Marginalia — Cuaderno Interactivo Marginalia Chapter 04 The Fundamental Operations

Since addition and subtraction are in principle the same operation with differing signs, the underlying algorithms are equivalent, and we can deal with them together in this section. (p. 24)

Expone la justificación metodológica del autor para consolidar el estudio de dos operaciones aparentemente distintas en un solo bloque conceptual, optimizando la arquitectura del software.

Desde la perspectiva del diseño de microchips y ALUs (Unidades Aritmético-Lógicas), la sustracción se ejecuta tradicionalmente como una adición tras calcular el complemento a dos del sustraendo. Al unificar los algoritmos, Welschenbach traslada esta eficiencia de hardware al software de precisión múltiple, sugiriendo que la lógica estructural profunda de bucles y gestión de acarreos/préstamos es simétrica.

where we assume \(a \geq b\). For addition this condition represents no restriction, since it can always be achieved by interchanging the two summands. For subtraction it means that the difference is positive or zero and therefore can be represented as a CLINT object without reduction modulo \((N_{max}+1)\). (p. 24)

Define una restricción matemática de entrada (precondition) que simplifica radicalmente el control de errores en las estructuras de datos de la biblioteca.

El tipo de dato CLINT almacena magnitudes enteras absolutas no negativas. Si el algoritmo permitiese subdesbordamientos aritméticos (\(a < b\) en una resta), el sistema experimentaría un comportamiento no deseado de envoltura modular bajo el módulo implícito del tamaño de almacenamiento de la biblioteca. Validar o forzar \(a \geq b\) actúa como un invariante de bucle que blinda el código contra estados inválidos.

The digits of the summands, together with the carry, are added in step 2, with the less-significant part stored as a digit of the sum, while the more-significant part is carried to the next digit. (p. 24)

Describe con precisión la técnica de segmentación de palabras mediante operaciones aritméticas enteras básicas (módulo y división) para simular la propagación de desbordamientos locales en software.

En un lenguaje de alto nivel como C, cuando la suma de dos palabras excede la capacidad de la base \(B\), el bit sobrante no se propaga automáticamente a nivel de registro de CPU de la misma forma que en ensamblador. El texto describe la simulación de este comportamiento aislando el residuo con el operador \(\bmod\) para el almacenamiento local y usando la división entera como un operador de desplazamiento a la derecha para extraer el acarreo puro.

El texto presenta formalmente la base del sistema numérico posicional de precisión múltiple y un algoritmo formal de adición. Desmenuzamos matemáticamente cada uno de sus componentes:

"leftover carry at the end, it is stored as the most-significant digit of the sum. The output of this digit is suppressed if it has the value zero." – Página 25

Es vital documentar esta regla porque define la normalización del formato del entero grande en memoria. Sin esta supresión de ceros a la izquierda, las funciones de comparación, serialización y cálculo modular fallarían al interpretar incorrectamente el tamaño real del número.

Un acarreo no es solo un bit volátil; se consolida físicamente en el arreglo del entero. No obstante, introduce una condición de poda para mantener la estructura compacta: si la adición del último par de dígitos no generó un acarreo neto (valor 0), el tamaño lógico del número se reduce para ignorar esa última posición de memoria vacía.

"Steps 2 and 4 of the algorithm appear in a similar form in the case of subtraction, multiplication, and division." – Página 25

Define la base de la reutilización de código y la homogeneidad en el diseño de toda la biblioteca multiprecisión. Nos ayuda a predecir cómo se comportarán los bucles internos de las siguientes funciones aritméticas del libro.

El control de punteros paso a paso (recorrer los dígitos de derecha a izquierda) y la normalización del tamaño lógico del resultado final siguen un esquema idéntico en las cuatro operaciones básicas, permitiendo inferir la arquitectura general del software a partir del análisis de la adición.

"The intermediate value t that appears in the algorithm is represented by the variable carry, of type ULONG, which holds the sum of the digits a_i and b_i, as well as the carry of the previous operation." – Página 25

Explica el mapeo directo entre la descripción abstracta del algoritmo matemático y las variables declaradas en C, resolviendo por qué se usa una variable llamada carry para almacenar una suma total.

Detalla un truco de implementación eficiente. En lugar de crear dos variables (una para la suma temporal de la posición y otra para el acarreo), la variable de tipo entero de largo de palabra doble (ULONG) asume simultáneamente ambas funciones gracias al almacenamiento lineal de la memoria y el espacio extra de bits.

La página presenta una línea de código matemática altamente compactada para el lenguaje C, cuya lógica es fundamental deconstruir bit a bit:

"The C expression in this compact form is due to my colleague Robert Hammelrath." – Página 25

/***********************************************************************
 * Fragmento extraído de la página 25: Inicialización de add_l()       *
 ***********************************************************************/

int add_l (CLINT a_l, CLINT b_l, CLINT s_l)
{
    clint ss_l[CLINTMAXSHORT + 1];
    clint *msdptra_l, *msdptrb_l;
    clint *aptr_l, *bptr_l, *sptr_l = LSDPTR_L (ss_l);
    ULONG carry = 0L;
    int OFL = E_CLINT_OK;

• El algoritmo necesita identificar de antemano cuál de los dos sumandos (a_l o b_l) posee el mayor número de dígitos criptográficos.
• Se definen dos pares de punteros con roles específicos:

  aptr_l y msdptra_l

  Apuntan, respectivamente, al dígito menos significativo (LSD) y al más significativo (MSD) del sumando de mayor longitud. En caso de empate en tamaño, toman por defecto las direcciones de a_l.

  bptr_l y msdptrb_l

  Apuntan al LSD y MSD del sumando de menor longitud. Si las longitudes son idénticas, toman por defecto las direcciones de b_l.

• Esta asimetría condicional garantiza que el bucle de adición principal solo necesite iterar hasta el final del número más corto, minimizando las instrucciones de control dentro de la sección más caliente del código (hot path).
• Adicionalmente, se establece la longitud temporal del arreglo de acumulación intermedio ss_l utilizando la macro de escritura SETDIGITS_L, igualándola al tamaño del sumando más largo.

• En el cuerpo del bucle, los dígitos de a_l y b_l se procesan secuencialmente y el resultado se almacena de forma contigua en el búfer temporal ss_l.
• El autor resalta una propiedad de seguridad aritmética: la presencia eventual de ceros a la izquierda (leading zeros) en los operandos no introduce fallos en el cómputo global. Son absorbidos aritméticamente por el bucle y posteriormente podados (filtrados) mediante normalización cuando el búfer intermedio ss_l es copiado hacia el destino final s_l.
• El bucle emula de forma estricta el algoritmo clásico de lápiz y papel, procesando de derecha a izquierda y propagando el bit de acarreo de forma contigua.

"The pointers aptr_l and msdptra_l are initialized such that they point respectively to the least-significant and most-significant digits of the sum-mand that has the most digits, or to those digits of a_l if both summands are of the same length." – Página 26

Esta regla documenta la optimización algorítmica central de la biblioteca. En lugar de comprobar en cada paso del bucle si un número se ha quedado sin dígitos, el compilador puede generar un bucle lineal directo indexado estrictamente por el puntero de parada del sumando más corto (msdptrb_l).

"Any leading zeros cause no problem, and they are simply used in the calculation and filtered out when the result is copied to s_l." – Página 26

Es una premisa de diseño de seguridad criptográfica fundamental. Garantiza que las funciones de la biblioteca toleren representaciones no canónicas de enteros grandes sin generar desbordamientos o estados corruptos en la memoria.

El proceso aritmético no discrimina si un dígito de peso alto es cero; lo suma siguiendo las reglas estándar. La responsabilidad de limpiar el número y devolverlo a su forma compacta canónica se delega por completo a la fase posterior de copia hacia s_l.

"The loop runs from the least-significant digit of b_l to the most-significant digit. This corresponds exactly to the process of pencil-and-paper addition as learned at school." – Página 26

Justifica la dirección del recorrido de la memoria (aritmética de punteros incremental hacia direcciones más altas) basándose en el diseño de almacenamiento Little-Endian de los dígitos en el arreglo CLINT.

Valida conceptualmente que la biblioteca implementa el algoritmo de adición de base estándar empezando por el orden de magnitud más bajo (\(2^0\)) y avanzando linealmente hacia la izquierda (\(2^{16n}\)), acumulando y arrastrando el acarreo.

El código inicializa dos estructuras con valores criptográficos simulados para verificar la ejecución del bucle.

• Si uno de los dos sumandos originales era estrictamente más largo que el otro, el bucle principal de la página 26 se detiene prematuramente. Quedan dígitos sin sumar en el operando largo.
• Se introduce un segundo bucle secuencial que procesa únicamente los dígitos restantes del sumando mayor (aptr_l) hasta alcanzar su dígito más significativo (msdptra_l).
• Aritméticamente, este bucle ya no realiza la adición de dos dígitos independientes; su propósito exclusivo es propagar el acarreo residual (carry) acumulado en las iteraciones previas a lo largo de las posiciones de memoria superiores.

• Tras agotar todos los dígitos de los operandos, el algoritmo evalúa si existe un acarreo neto remanente al final de la operación mediante una comparación lógica de bits contra la constante BASE (equivalente a la frontera de desbordamiento \(2^{16}\)).
• Si el acarreo final es afirmativo, el número resultante es exactamente un dígito más largo que el sumando original de mayor tamaño. El bit de acarreo se escribe físicamente en la memoria en la posición *sptr_l y se incrementa en uno la cabecera de longitud lógica del número empleando SETDIGITS_L.

• La biblioteca impone un límite rígido de capacidad mediante la constante de configuración CLINTMAXDIGIT. Si la adición del acarreo final provoca que la longitud lógica del número supere este límite físico de almacenamiento, ocurre un desbordamiento catastrófico.
• Para evitar la corrupción de memoria y mantener la consistencia aritmética, se invoca la función de reducción ANDMAX_L(), la cual ejecuta una reducción matemática del entero grande bajo el módulo \((N_{max} + 1)\), truncando los bits excedentes inseguros.
• El estado de error muta formalmente a E_CLINT_OFL para indicar el fallo al hilo de ejecución superior. Finalmente, el búfer de trabajo seguro ss_l se transfiere al espacio de memoria destino s_l por medio de cpy_l().

"In the second loop only the remaining digits of a_l are added to a possible existing carry and stored in s_l." – Página 27

Esta línea define conceptualmente la transición aritmética del algoritmo. Es vital documentar que el bucle se vuelve unario (un solo operando más la variable de control) debido al diseño de optimización de punteros asimétricos planteado en la página 26.

El segundo bucle asume que el operando b_l ya fue agotado en su totalidad. Por lo tanto, las celdas de memoria del búfer destino ss_l (representado por sptr_l) se rellenan exclusivamente con el valor de los dígitos superiores de a_l a los cuales se les inyecta el residuo matemático que se arrastra en la variable carry.

"If after the second loop there is a carry, the result is one digit longer than a_l. If it is determined that the result exceeds the maximal value N_max representable by the CLINT type, then the result is reduced modulo (N_max + 1)" – Página 27

Es el núcleo de la seguridad criptográfica de la biblioteca. Documenta de forma explícita el punto de ruptura del almacenamiento físico de datos y el método algebraico para contenerlo de forma segura dentro de los límites del arreglo.

Detalla las dos consecuencias de un acarreo persistente al final del proceso de lápiz y papel. Primero, el número se expande físicamente una palabra hacia la izquierda. Segundo, introduce la bifurcación de seguridad: si esta expansión viola el tamaño límite (CLINTMAXDIGIT), el número entra en un estado de desbordamiento clásico de anillo aritmético, aplicando una operación de módulo para truncar los bits superiores que la CPU ya no puede indexar de forma segura en la estructura.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef uint16_t clint;
typedef uint16_t USHORT;
typedef uint64_t ULONG;

#define CLINTMAXSHORT 24096
#define BITPERDIGIT   16
#define CLINTMAXDIGIT 24096
#define BASE          0x10000L

typedef clint CLINT[CLINTMAXSHORT + 2];

#define DIGITS_L(x)      (*(x))
#define SETDIGITS_L(x,n) (*(x) = (clint)(n))
#define LSDPTR_L(x)      ((clint *)(x) + 1)
#define MSDPTR_L(x)      ((clint *)(x) + *(x))

#define E_CLINT_OK   0
#define E_CLINT_OFL  -1

int add_l (CLINT a_l, CLINT b_l, CLINT s_l);
void ANDMAX_L (CLINT src_l);
void cpy_l (CLINT dest_l, CLINT src_l);

void ANDMAX_L (CLINT src_l) {
  SETDIGITS_L(src_l, CLINTMAXDIGIT);
}

void cpy_l (CLINT dest_l, CLINT src_l) {
  clint i;
  for (i = 0; i <= DIGITS_L(src_l); i++) {
    dest_l[i] = src_l[i];
  }
}

int add_l (CLINT a_l, CLINT b_l, CLINT s_l) {
  clint ss_l[CLINTMAXSHORT + 1];
  clint *msdptra_l, *msdptrb_l;
  clint *aptr_l, *bptr_l, *sptr_l = LSDPTR_L (ss_l);
  ULONG carry = 0L;
  int OFL = E_CLINT_OK;

  if (DIGITS_L (a_l) < DIGITS_L (b_l)) {
    aptr_l = LSDPTR_L (b_l);
    bptr_l = LSDPTR_L (a_l);
    msdptra_l = MSDPTR_L (b_l);
    msdptrb_l = MSDPTR_L (a_l);
    SETDIGITS_L (ss_l, DIGITS_L (b_l));
  } else {
    aptr_l = LSDPTR_L (a_l);
    bptr_l = LSDPTR_L (b_l);
    msdptra_l = MSDPTR_L (a_l);
    msdptrb_l = MSDPTR_L (b_l);
    SETDIGITS_L (ss_l, DIGITS_L (a_l));
  }

  while (bptr_l <= msdptrb_l) {
    *sptr_l++ = (clint)(USHORT)(carry = (ULONG)*aptr_l++ + (ULONG)*bptr_l++ + (ULONG)(USHORT)(carry >> BITPERDIGIT));
  }

  while (aptr_l <= msdptra_l) {
    *sptr_l++ = (clint)(USHORT)(carry = (ULONG)*aptr_l++ + (ULONG)(USHORT)(carry >> BITPERDIGIT));
  }

  if (carry >= BASE) {
    *sptr_l = 1;
    SETDIGITS_L (ss_l, DIGITS_L (ss_l) + 1);
  }

  if (DIGITS_L (ss_l) > (USHORT)CLINTMAXDIGIT) {
    ANDMAX_L (ss_l);
    OFL = E_CLINT_OFL;
  }

  cpy_l (s_l, ss_l);
  return OFL;
}

int main(void) {
  CLINT a = {0}, b = {0}, resultado = {0};

  SETDIGITS_L(a, 2);
  a[1] = 0xFFFF;
  a[2] = 0xFFFF;

  SETDIGITS_L(b, 1);
  b[1] = 0x0001;

  printf("[GENTOO-SYS] Ejecutando suma completa de la pagina 27...\n");
  int status = add_l(a, b, resultado);
  printf("[GENTOO-SYS] Longitud del resultado final obtenido: %u\n", (unsigned int)DIGITS_L(resultado));
  printf("[GENTOO-SYS] Estado final de desbordamiento (OFL): %d\n", status);

  return status == E_CLINT_OK ? EXIT_SUCCESS : EXIT_FAILURE;
}

while (aptr_l <= msdptra_l)

Este segundo bucle procesa exclusivamente el operando remanente de mayor longitud (aptr_l). La expresión aritmética interna prescinde de la lectura de un segundo dígito y suma directamente el acarreo desplazado de 16 bits (carry >> BITPERDIGIT) a la palabra actual. El puntero de destino sptr_l avanza linealmente.

if (carry >= BASE)

Verifica si la última suma efectuada generó un acarreo neto que desborda la base del sistema numérico multiprecisión de 16 bits. La constante BASE está tipada como 0x10000L (65536). Si se cumple, el residuo se almacena forzadamente en la memoria (*sptr_l = 1) y la macro SETDIGITS_L actualiza la cabecera lógica incrementando la longitud del arreglo en un dígito adicional.

if (DIGITS_L (ss_l) > (USHORT)CLINTMAXDIGIT)

Evaluación del límite crítico de almacenamiento del tipo de datos CLINT. Si el crecimiento provocado por el acarreo rompe la restricción de hardware (CLINTMAXDIGIT), el entero grande es inyectado en ANDMAX_L para truncar los bits superiores mediante reducción modular aritmética, alterando el estado de retorno de la función a la constante de error E_CLINT_OFL.

# Escenario 1: Producción Optimizada (USE="hardened -debug")
gcc -O3 -pipe -march=native -fno-plt \
    -fstack-protector-strong -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=3 -fPIE \
    -Wl,-O1,-z,relro,-z,now,--as-needed -pie \
    clint_add_l2.c -o clint_optimized2

# Escenario 2: Análisis Avanzado de Memoria (USE="hardened debug")
gcc -O0 -g3 -ggdb -pipe -march=native \
    -fsanitize=address -fsanitize=undefined -fsanitize=pointer-compare -fsanitize=pointer-subtract \
    -fstack-protector-all -fPIE -DDEBUG \
    -Wl,-z,relro,-z,now -pie \
    clint_add_l2.c -o overflow_sanitized2

# Escenario 3: Análisis Estático Estricto (Filtro de Calidad Máxima de GCC)
gcc -O2 -pipe -march=native \
    -Wall -Wextra -Werror -Wpedantic -Wstrict-prototypes -Wmissing-prototypes \
    -Wshadow -Wconversion -Wsign-conversion -Wcast-align=strict -Wundef \
    clint_add_l2.c -o clint_generic2

Las trazas de ejecución en la terminal de Gentoo confirman el comportamiento aritmético exacto planteado en la arquitectura del libro:

[GENTOO-SYS] Ejecutando suma completa de la pagina 27...
[GENTOO-SYS] Longitud del resultado final obtenido: 3
[GENTOO-SYS] Estado final de desbordamiento (OFL): 0

• Los operandos se descomponen posicionalmente en base \(B\) según sus longitudes lógicas: \(a = (a_{m-1}a_{m-2}\dots a_0)_B\) y \(b = (b_{n-1}b_{n-2}\dots b_0)_B\).
• El algoritmo se ejecuta en dos grandes fases secuenciales parametrizadas por un contador de dígitos \(i\) y una variable de control de préstamo o "acarreo inverso" \(c\):
  • Fase de Inicialización: Se establece el índice base \(i \leftarrow 0\) y se asume inicialmente la ausencia de deuda aritmética fijando \(c \leftarrow 1\) (donde \(c=1\) indica sin préstamo y \(c=0\) denota préstamo activo).
  • Primer Bucle (Pasos 2 al 4): Modula la resta columna por columna hasta agotar los dígitos del sustraendo más corto (\(n-1\)). Si hay préstamo activo (\(c=1\)), el valor intermedio es \(t \leftarrow B + a_i - b_i\); de lo contrario, se calcula como \(t \leftarrow B - 1 + a_i - b_i\). El dígito resultante se extrae mediante \(d_i \leftarrow t \pmod B\), actualizando el préstamo con la división entera \(c \leftarrow \lfloor t / B \rfloor\).
  • Segundo Bucle (Pasos 5 al 7): Propaga de forma unaria el préstamo remanente a lo largo de los dígitos superiores del minuendo (\(a_i\)) desde el índice \(n\) hasta \(m-1\).
  • Fase de Salida: El resultado se consolida vectorialmente en la estructura destino como \(d = (d_{m-1}d_{m-2}\dots d_0)_B\).

• La biblioteca criptográfica preserva la estructura de punteros asimétricos analizada en la adición, pero altera semánticamente el rol de las variables intermedios.
• El Préstamo (Borrow): La variable temporal carry (de tipo ULONG) permuta su función para actuar como el "préstamo" (borrow). Este registro extrae una unidad de la base del dígito inmediatamente superior del minuendo cuando la resta local de una columna produce un residuo negativo (\(a_i < b_i\)).
• El Subdesbordamiento (Underflow): A diferencia de la adición, donde el peligro latente es el desbordamiento por exceso de bits (overflow), la sustracción criptográfica vigila el subdesbordamiento (underflow). Si la condición inicial \(a \geq b\) se viola en tiempo de ejecución, el resultado aritmético real caería en el espectro de los números negativos. Dado que el tipo CLINT representa un entero estrictamente sin signo (unsigned), el sistema absorbe el impacto aplicando una reducción algebraica bajo el módulo \((N_{max} + 1)\) y alterando el estado de retorno de la función al código de error formal E_CLINT_UFL.
• Poda Canónica: Al concluir la copia, cualquier residuo de ceros remanentes en las posiciones de peso alto (leading zeros) se elimina dinámicamente de la cabecera del entero.

"The ULONG variable carry is used to “borrow” from the next-higher digit of the minuend if a digit of the minuend is smaller than the corresponding digit of the subtrahend." – Página 28

Documenta la reutilización de la infraestructura física de registros de la biblioteca. En lugar de crear variables adicionales, el diseño criptográfico aprovecha la palabra ancha de carry para modelar la deuda aritmética entre columnas consecutivas del entero multiprecisión.

El mecanismo de préstamo analógico al cálculo clásico de lápiz y papel pasara a mostrarnos que si en una columna dada el sustraendo supera al minuendo (\(a_i < b_i\)), la operación local es inválida en aritmética sin signo de un solo dígito. La variable de control carry interviene alterando su estado para arrastrar y descontar ese bit en la iteración inmediatamente superior de la memoria de la pila.

"Instead of an overflow one must be on the lookout for a possible underflow, in which case the result of the subtraction would actually be negative; however, since CLINT is an unsigned type, there will be a reduction modulo (N_max + 1) (see Chapter 5). The function returns the error code E_CLINTUFL to indicate this situation." – Página 28

Establece el principio algebraico que rige el manejo de errores en operaciones no canónicas con enteros sin signo dentro de la biblioteca. Define el mapeo exacto del código de error E_CLINT_UFL.

A su vez este explica el comportamiento ante condiciones de contorno inválidas. Si la resta da un número negativo, el hardware de la CPU provocaría un ciclo de envoltura (wrap-around) descontrolado. Para mitigar esto, la biblioteca implementa de forma explícita el comportamiento del anillo modular \(\mathbb{Z}_{N_{max}+1}\). El número se trunca matemáticamente para que quepa en el arreglo, pero se activa un centinela de advertencia (E_CLINT_UFL) para alertar a las capas de abstracción superiores sobre la invalidez matemática del resultado.

Esta sección detalla la ejecución del flujo de control y las operaciones de bajo nivel de la función de sustracción criptográfica sub_l(). El algoritmo procesa los operandos mediante aritmética de punteros, gestiona de forma unaria los dígitos sobrantes del minuendo, normaliza la estructura final y aplica la corrección algebraica en anillo si ocurrió un subdesbordamiento.

"The required addition of (minuend + 1) to the difference N_max - b_l stored in d_l is carried out before the output of d_l." – Página 30

Esta instrucción documenta la justificación algebraica del diseño de la biblioteca. Dado que el tipo CLINT es estrictamente sin signo (unsigned), no puede almacenar un signo negativo flotante. La cita fundamenta matemáticamente por qué la biblioteca calcula primero la distancia al límite de saturación y luego inyecta el minuendo más la unidad para forzar la envoltura modular de forma segura.

Es asi como se detalla la corrección en el cierre de la función. Si el minuendo era menor, el bucle procesó \((N_{max} - b\_l)\). Al salir, el software concatena las llamadas de add_l y inc_l para reconstruir de manera opaca la congruencia matemática modular exacta antes de exponer el resultado al llamador.

"In addition to the functions add_l() and sub_l() two special functions for addition and subtraction are available, which operate on a USHORT as the second argument instead of a CLINT. These are called mixed functions and identified by a function name with a prefixed “u,”" – Página 30

Explica la justificación de rendimiento detrás del mapa de la API. Evita que el programador desperdicie ciclos de reloj de la pila creando arreglos completos multiprecisión para sumarle o restarle una constante pequeña de 16 bits a un entero criptográfico grande.

El autor introduce optimizaciones nativas de bajo nivel. Al anteponer la letra "u", se le indica al compilador que aplique una lógica simplificada donde el bucle de adición o sustracción de columnas se reduce a una sola iteración elemental de hardware, propagando inmediatamente después el acarreo o préstamo.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef uint16_t clint;
typedef uint16_t USHORT;
typedef uint64_t ULONG;

#define CLINTMAXSHORT 24096
#define BITPERDIGIT   16
#define CLINTMAXDIGIT 24096
#define BASE          0x10000L

typedef clint CLINT[CLINTMAXSHORT + 2];

#define DIGITS_L(x)      (*(x))
#define SETDIGITS_L(x,n) (*(x) = (clint)(n))
#define LSDPTR_L(x)      ((clint *)(x) + 1)
#define MSDPTR_L(x)      ((clint *)(x) + *(x))

#define E_CLINT_OK   0
#define E_CLINT_UFL  -2

int sub_l (CLINT aa_l, CLINT bb_l, CLINT d_l);
int add_l (CLINT a_l, CLINT b_l, CLINT s_l);
void inc_l (CLINT src_l);
int LT_L (CLINT a_l, CLINT b_l);
void setmax_l (CLINT src_l);
void RMLDZRS_L (CLINT src_l);
void cpy_l (CLINT dest_l, CLINT src_l);

int LT_L (CLINT a_l, CLINT b_l) {
  if (DIGITS_L(a_l) < DIGITS_L(b_l)) return 1;
  if (DIGITS_L(a_l) > DIGITS_L(b_l)) return 0;
  return a_l[DIGITS_L(a_l)] < b_l[DIGITS_L(b_l)];
}

void setmax_l (CLINT src_l) {
  clint i;
  SETDIGITS_L(src_l, CLINTMAXDIGIT);
  for (i = 1; i <= CLINTMAXDIGIT; i++) {
    src_l[i] = 0xFFFF;
  }
}

void RMLDZRS_L (CLINT src_l) {
  clint len = DIGITS_L(src_l);
  while (len > 0 && src_l[len] == 0) {
    len--;
  }
  SETDIGITS_L(src_l, len);
}

void cpy_l (CLINT dest_l, CLINT src_l) {
  clint i;
  for (i = 0; i <= DIGITS_L(src_l); i++) {
    dest_l[i] = src_l[i];
  }
}

int add_l (CLINT a_l, CLINT b_l, CLINT s_l) {
  (void)a_l; (void)b_l; (void)s_l;
  return E_CLINT_OK;
}

void inc_l (CLINT src_l) {
  (void)src_l;
}

int sub_l (CLINT aa_l, CLINT bb_l, CLINT d_l) {
  CLINT a_l, b_l;
  clint *msdptra_l, *msdptrb_l;
  clint *aptr_l, *bptr_l, *dptr_l = LSDPTR_L (d_l);
  ULONG carry = 0L;
  int UFL = E_CLINT_OK;

  cpy_l (a_l, aa_l);
  cpy_l (b_l, bb_l);

  if (LT_L (a_l, b_l)) {
    setmax_l (a_l);
    msdptra_l = MSDPTR_L (a_l);
    SETDIGITS_L (d_l, CLINTMAXDIGIT);
    UFL = E_CLINT_UFL;
  } else {
    SETDIGITS_L (d_l, DIGITS_L (a_l));
  }

  aptr_l = LSDPTR_L (a_l);
  bptr_l = LSDPTR_L (b_l);
  msdptra_l = MSDPTR_L (a_l);
  msdptrb_l = MSDPTR_L (b_l);

  while (bptr_l <= msdptrb_l) {
    *dptr_l++ = (clint)(USHORT)(carry = (ULONG)*aptr_l++ - (ULONG)*bptr_l++ - ((carry & BASE) >> BITPERDIGIT));
  }

  while (aptr_l <= msdptra_l) {
    *dptr_l++ = (clint)(USHORT)(carry = (ULONG)*aptr_l++ - ((carry & BASE) >> BITPERDIGIT));
  }

  RMLDZRS_L (d_l);

  if (UFL) {
    add_l (d_l, aa_l, d_l);
    inc_l (d_l);
  }

  return UFL;
}

int main(void) {
  CLINT a = {0}, b = {0}, resultado = {0};

  SETDIGITS_L(a, 1);
  a[1] = 0x0005;

  SETDIGITS_L(b, 1);
  b[1] = 0x0002;

  printf("[GENTOO-SYS] Iniciando ejecucion de la sustraccion de la pagina 30\n");
  int status = sub_l(a, b, resultado);
  printf("[GENTOO-SYS] Longitud de la diferencia calculada: %u\n", (unsigned int)DIGITS_L(resultado));
  printf("[GENTOO-SYS] Estado final del flag de prestamo (UFL): %d\n", status);

  return status == E_CLINT_OK ? EXIT_SUCCESS : EXIT_FAILURE;
}

La línea central del bucle utiliza aritmética de punteros con efectos colaterales e inversión lógica binaria:

*dptr_l++ = (clint)(USHORT)(carry = (ULONG)*aptr_l++ - (ULONG)*bptr_l++ - ((carry & BASE) >> BITPERDIGIT));

carry & BASE

Aplica una máscara binaria utilizando 0x10000L (el bit número 16 de un entero largo). Si la sustracción anterior de la columna inferior requirió un préstamo (borrow), este bit estará encendido debido al desbordamiento negativo controlado del tipo de dato sin signo de 64 bits.

>> BITPERDIGIT

Desplaza el bit filtrado 16 posiciones hacia la derecha. Esto colapsa el valor de la máscara (0x10000) a una unidad escalar pura (1 o 0), mapeando perfectamente la deuda matemática que debe ser descontada aritméticamente en el dígito actual de la pila.

carry = (ULONG)...

Resta secuencialmente los componentes y almacena el resultado intermedio completo en la palabra ancha de 64 bits. Si la columna actual no tiene suficiente magnitud (\(a_i < b_i + préstamo\)), la CPU activa automáticamente el bit superior número 16, propagando de manera transparente la deuda para la siguiente iteración.

La implementación técnica en C de las funciones mixtas uadd_l() y usub_l(). El propósito de este diseño de API es interceptar argumentos mixtos (un entero grande CLINT combinado con un entero corto nativo de hardware USHORT), permitiendo operar escalares de forma directa sin obligar al programador a instanciar manualmente objetos multiprecisión complejos.

"Function: mixed addition of a CLINT type and a USHORT type Syntax: int uadd_l (CLINT a_l, USHORT b, CLINT s_l);" – Página 31

Define la sintaxis rígida y el contrato de tipado de la interfaz de usuario de la biblioteca criptográfica. Documenta el desacoplamiento de tipos necesarios para que el compilador no genere advertencias de conversión de punteros.

El segundo argumento ya no es una referencia a un arreglo de memoria (CLINT), sino un paso por valor puro de 16 bits (USHORT). El resultado final mantiene la consistencia multiprecisión al escribirse en un arreglo tradicional de destino (s_l).

"Function: subtraction of a USHORT type from a CLINT type Syntax: int usub_l (CLINT a_l, USHORT b, CLINT d_l);" – Página 31

Esta cita es clave para evidenciar que el orden de los operandos es estrictamente asimétrico y rígido: el minuendo siempre debe ser el entero grande multiprecisión y el sustraendo el escalar de hardware.

Esta parte entonces pasara a detallar los límites semánticos de la función. No está diseñada para restar un número grande de uno corto (\(b - a\_l\)); su lógica asume de manera obligatoria que se está drenando una magnitud pequeña (\(b\)) de una estructura de alta capacidad (\(a\_l\)).

• Las funciones inc_l() y dec_l() incrementan o decrementan el valor de un objeto CLINT en exactamente 1.
• A diferencia de add_l() o sub_l(), estas rutinas están diseñadas estructuralmente como rutinas acumuladoras: el operando de entrada (a_l) es sobreescrito directamente en memoria con el valor del resultado, eliminando la necesidad de un búfer o arreglo de destino independiente.
• Las funciones replican la lógica de control de errores de la biblioteca: validan estados de desbordamiento por exceso (overflow) o por defecto (underflow) y retornan las constantes de error estándar E_CLINT_OFL y E_CLINT_UFL respectivamente.

• El núcleo de inc_l() inicializa la variable carry con el valor de la constante BASE (0x10000L) para inyectar el incremento inicial de una unidad en la posición del dígito menos significativo.
• El bucle de procesamiento while (aptr_l <= msdptra_l && (carry & BASE)) introduce una optimización crítica en el flujo caliente (hot path): el ciclo se interrumpe de manera inmediata (short-circuit) en cuanto el acarreo se extingue (carry & BASE se evalúa como falso). Esto evita recorrer innecesariamente el resto de los dígitos superiores del entero largo si no hay más acarreos que propagar.
• Dentro del bucle, el dígito actual se promueve a 64 bits y se actualiza sumándole el acarreo previo desplazado. El resultado se trunca a 16 bits para sobrescribir la posición física.

• Si el bucle se agota y el acarreo persiste más allá del dígito más significativo (aptr_l > msdptra_l && (carry & BASE)), el número experimenta una expansión física. Se escribe un 1 en la siguiente palabra de memoria y se incrementa en uno el tamaño lógico del entero en su cabecera usando SETDIGITS_L.
• Si este crecimiento provoca que el tamaño lógico supere la constante límite CLINTMAXDIGIT, la función activa el mecanismo de mitigación de desbordamientos: invoca SETZERO_L(a_l) para reducir el número bajo el módulo \((N_{max} + 1)\), mutando el estado de retorno a E_CLINT_OFL.

"These functions are designed as accumulator routines: The operand is overwritten with the return value, which has proved practical in the implementation of many algorithms." – Página 32

Esta afirmación documenta una decisión fundamental de diseño de software criptográfico dentro de la biblioteca. Justifica la ausencia de un tercer argumento de destino en la firma de la función, optimizando el uso de la pila de memoria al reciclar la estructura de datos existente.

El autor detalla que, para algoritmos criptográficos complejos (como la exponenciación modular o el algoritmo de Euclides), es computacionalmente costoso mantener copias de búferes intermedios. Diseñar inc_l para que actúe directamente sobre el registro de memoria original incrementa la localidad de los datos en la caché del procesador y reduce los ciclos de reloj asociados al copiado de arreglos.

"It is not surprising that the implementations of inc_l() and dec_l() are similar to those of the functions add_l() and sub_l(). They test for overflow and underflow, respectively, and return the corresponding error codes E_CLINTOFL and E_CLINTUFL." – Página 32

Establece el principio de consistencia arquitectónica de la API. Garantiza que las rutinas de mutación unitaria hereden de forma estricta las mismas políticas y salvaguardas algebraicas de manejo de desbordamientos que las funciones aritméticas binarias completas.

Explica que, aunque un incremento de una sola unidad parece una operación menor, matemáticamente comparte los mismos límites de frontera que una suma multiprecisión regular. Si el entero ya se encuentra en su estado de saturación máxima, sumarle uno rompe la capacidad del arreglo y requiere de manera mandatoria la misma respuesta defensiva: reducción por módulo y alerta mediante flags de error.

• Interfaz y Comportamiento: La función int dec_l (CLINT a_l) resta exactamente una unidad al entero grande de forma destructiva sobreescribiendo el operando de entrada. Retorna E_CLINT_OK o E_CLINT_UFL si detecta subdesbordamiento.
• Fase de Inicialización: El puntero aptr_l se posiciona en el dígito menos significativo (LSD). La variable de control carry se inicializa con la constante de hardware BASEMINONE (0xFFFFL), la cual representa la máscara semántica de deuda unitaria para el sistema.
• Control Preventivo de Underflow: Antes de iterar, la macro EQZ_L(a_l) (Equal Zero) evalúa si el número es estrictamente cero. De cumplirse, restar uno provocaría un bucle negativo inválido. La función se defiende invocando setmax_l(a_l) para forzar una envoltura modular saturando el arreglo con el valor \(N_{max}\) y rompe la ejecución retornando E_CLINT_UFL.

• El ciclo while ((aptr_l <= msdptra_l) && (carry & (BASEMINONE << BITPERDIGIT))) gestiona la propagación de la deuda. La condición de parada incluye un cortocircuito (short-circuit) idéntico al de inc_l(): si el bit de préstamo se extingue en las posiciones bajas, el bucle se detiene de inmediato.
• En cada iteración, la expresión aritmética resta el dígito actual promovido de un valor derivado de la base, actualizando carry y guardando el residuo de 16 bits truncado mediante (USHORT).
• Al salir, la macro RMLDZRS_L(a_l) remueve vectorialmente cualquier cero a la izquierda generado por la operación para normalizar el tamaño lógico de la estructura.

• El libro abre el apartado con una cita de Leopold Kronecker (On the Idea of Number) que define matemáticamente la multiplicación como una adición repetida de sumandos idénticos (\(n_1 + n_2 + \dots + n_r = rn\)).
• El autor subraya que la multiplicación es la operación más crítica de todo el paquete FLINT/C. Debido a que algoritmos de capas superiores (como la exponenciación modular de RSA o Diffie-Hellman) invocan esta rutina miles de veces, el tiempo de computo de la multiplicación (junto con la división) dicta de forma directa el rendimiento y la latencia total de la biblioteca de software.

"if (EQZ_L (a_l)) /* underflow? //* { setmax_l (a_l); /* reduce modulo max₁ /* return E_CLINTUFL; }" – Página 33

Esta sección del código es vital porque ilustra la implementación exacta de la aritmética de anillos modulares para el decremento en el tipo sin signo CLINT. Documenta la bifurcación defensiva primaria de la rutina acumuladora.

Detalla que si el llamador intenta decrementar el valor cero (\(0 - 1\)), el hardware de la CPU generaría un estado inválido o corrupto en una estructura multiprecisión sin signo. La biblioteca intercepta este caso, transforma el objeto de forma destructiva en el número más grande representable (\(N_{max}\)) para emular la envoltura de \(\mathbb{Z}_{N_{max}+1}\) y alerta a la aplicación mediante el flag de error E_CLINT_UFL.

"Multiplication is one of the most critical functions of the entire FLINT/C package due to the computation time required for its execution, since together with division it determines the execution time of many algorithms." – Página 33

Provee la justificación de diseño de ingeniería de software para las optimizaciones complejas en ensamblador que se estudiarán en las siguientes páginas. Explica el porqué del costo computacional de este bloque de funciones.

El autor establece que la eficiencia de la biblioteca no se mide en la velocidad de sus sumas, sino en la velocidad de su multiplicación. Al ser la base de las operaciones de campo y anillos criptográficos, optimizar este componente a nivel de registros físicos de la CPU tiene un impacto multiplicativo en la aceleración del hardware.

• Las operaciones previas de adición y sustracción multiprecisión se ejecutan en tiempo lineal \(O(n)\) respecto al número de dígitos de los argumentos. Sin embargo, los algoritmos clásicos de multiplicación y división requieren un tiempo de ejecución cuadrático \(O(n^2)\) o \(O(m \cdot n)\) donde \(m\) y \(n\) son las longitudes de los operandos.
• Esta disparidad computacional convierte a la multiplicación en el cuello de botella central, motivando la célebre pregunta de Donald Knuth en su literatura fundamental: "How fast can we multiply?" (¿Qué tan rápido podemos multiplicar?).

• Para enteros de proporciones masivas, existen procedimientos de alta complejidad algebraica. El texto destaca el algoritmo de A. Schönhage y V. Strassen, el cual emplea la Transformada Rápida de Fourier (FFT) sobre campos finitos (anillos de enteros).
• La cota superior asintótica de este método está estrictamente delimitada por la función de complejidad: \[O(n \log n \log \log n)\]
• Límite de Viabilidad: A pesar de su superioridad teórica, el algoritmo de Schönhage-Strassen posee una constante oculta muy elevada. Su ventaja de rendimiento real sobre el método clásico de \(O(n^2)\) solo se manifiesta cuando los operandos superan un umbral de tamaño de entre 8,000 y 10,000 bits binarios. Dado que los sistemas criptográficos estándar contemplados por la biblioteca operan por debajo de este rango, este método excede el dominio de aplicación práctica de las funciones actuales.

• La biblioteca criptográfica selecciona dos pilares para su implementación:
  • Algoritmo M de Knuth: El método escolar tradicional indexado por punteros, optimizado para longitudes pequeñas y moderadas.
  • Multiplicación de Karatsuba: Un algoritmo de división y conquista que rompe la barrera cuadrática, operando con una complejidad asintótica de \(O(n^{\log_2 3}) \approx O(n^{1.585})\), ofreciendo un ahorro drástico en el cómputo de multiplicaciones y cuadrados de precisión intermedia.

"These techniques encompass the fastest known multiplication algorithms, but their advantage in speed over the classical O(n²) methods comes into play only when the number of binary digits is in the range 8,000–10,000. Based on the demands of cryptographic systems, such numbers, at least for the present, are far beyond the range envisioned in the application domain of our functions." – Página 34

Esta afirmación proporciona la justificación de ingeniería de software para descartar la implementación de algoritmos basados en FFT dentro de la biblioteca criptográfica. Delimita los límites físicos y las demandas del dominio de la seguridad criptográfica frente a la teoría matemática pura.

El autor detalla que los algoritmos de multiplicación por FFT son los más rápidos del mundo en términos asintóticos, pero sufren de una sobrecarga de inicialización masiva. En criptografía de clave pública convencional (como RSA o ECC), los tamaños de clave oscilan comúnmente entre 256 y 4096 bits. Intentar inyectar FFT en este espectro resultaría en un rendimiento significativamente inferior al del algoritmo cuadrático estándar debido a que no se ha alcanzado el punto de cruce en la curva de eficiencia.

"For our realization of multiplication for the FLINT/C package we would like first to use as a basis the grade school method based on “Algorithm M” given by Knuth… and finally look at the multiplication procedure of Karatsuba, which is asymptotically better than O(n²)." – Página 34

Documenta el mapa de ruta arquitectónico para el desarrollo del núcleo aritmético del paquete. Explica la coexistencia de un algoritmo clásico y un algoritmo de división y conquista dentro del mismo sistema de software.

Esto es importante porque la biblioteca no se ata a una única solución. El "Algoritmo M" de Knuth provee la estabilidad y la velocidad óptima en palabras de memoria de tamaño reducido, mientras que el procedimiento de Karatsuba se introduce como una optimización avanzada para interceptar enteros intermedios, reduciendo el número de multiplicaciones escalares de hardware de cuatro a tres por cada bloque.

La sección 4.2.1 The Grade School Method formaliza la estructura de los números enteros grandes antes de la operación de multiplicación. Es imperativo desmenuzar las sumatorias vectoriales polinómicas para comprender la indexación de memoria posterior:

• La figura 4-1 ilustra el cálculo para \(m = n = 3\). En ella se observa la generación de los productos parciales \((a_2a_1a_0)_B \cdot b_j\) para cada dígito del multiplicador (\(j = 0, 1, 2\)).
• Cada término elemental se descompone en un valor binómico: los dígitos de menor peso \(p_{2j}, p_{1j}, p_{0j}\) (denominados "Inner products" o productos internos, calculados como \(a_i \cdot b_j + \text{carry}\)) y los acarreos de mayor peso \(c_{2j}, c_{1j}, c_{0j}\) que se propagan hacia la izquierda.
• Al final de la matriz, las columnas de productos parciales escalados se suman vectorialmente para consolidar el producto completo \(p = (p_5p_4p_3p_2p_1p_0)_B\).

• Una implementación directa de la ecuación general \(p = \sum_{j=0}^{n-1}\sum_{i=0}^{m-1} a_i b_j B^{i+j}\) requeriría calcular y almacenar por separado cada producto parcial, para luego realizar una gran suma multiprecisión final. Esto resulta computacionalmente ineficiente y costoso en memoria para un programa de computadora.

• La Alternativa Eficiente: El algoritmo real adopta una estrategia de acumulación in situ. Consiste en sumar el producto elemental \(a_i \cdot b_j\) directamente sobre el valor ya existente en la celda de memoria del resultado (\(p_{i+j}\)), incorporando el acarreo \(c\) de los pasos previos. La ecuación de actualización local que se ejecuta en el núcleo del bucle es:

  \[t \leftarrow p_{i+j} + a_i b_j + c\]

• El número total de multiplicaciones de precisión simple necesarias para completar la operación está rígidamente acotado por el producto de las longitudes de los operandos: \(m \cdot n\).

• El valor intermedio de 64 bits \(t\) se descompone matemáticamente en una estructura de base \(B\): \(t = k \cdot B + l\), donde \(l\) representa el nuevo dígito criptográfico filtrado (\(0 \leq l < B\)) que sobrescribe a \(p_{i+j}\), y \(k\) pasa a ser el nuevo acarreo para el siguiente ciclo (\(c \leftarrow k\)).
• El autor demuestra rigurosamente mediante inecuaciones que el valor máximo de \(t\) jamás superará el límite del espacio de memoria de un solo dígito de acarreo de hardware. El peor escenario teórico asume que todas las variables están saturadas en su valor límite superior (\(B - 1\)), demostrando algebraicamente que el acarreo \(k\) siempre se mantendrá estrictamente menor que la base \(B\).

"A multiplication function that followed exactly the schema outlined above would first calculate all partial products, store these values, and then sum them up, each provided with the appropriate scaling factor. This school method is quite suitable for calculating with pencil and paper, but for the possibilities of a computer program it is somewhat cumbersome." – Página 35

La justificación arquitectónica para rechazar la transposición directa del algoritmo de escuela al código fuente de C. Explica la necesidad de rediseñar el flujo del algoritmo para adaptarlo a la eficiencia de los registros de la CPU.

El almacenamiento temporal de filas de productos parciales genera una sobrecarga innecesaria en la memoria caché del procesador. El software criptográfico debe mutar este comportamiento secuencial y transformarlo en un ciclo de acumulación entrelazado, reduciendo las operaciones de escritura y reutilizando las mismas posiciones del arreglo destino de forma inmediata.

"A more efficient alternative consists in adding the inner products a_i b_j at once to the accumulated values in the result digit p_i+j, to which are added the carries c from previous steps." – Página 35

Esta afirmación establece formalmente la regla de diseño para el bucle de multiplicación que poblará el código en las siguientes páginas. Define la fusión de la multiplicación y la adición en un único paso de hardware.

La celda de destino \(p_{i+j}\) no se limita a recibir un valor, sino que actúa como un acumulador activo. El procesador lee el valor residente en esa posición, le añade el producto de los dígitos actuales del multiplicando y multiplicador, suma el acarreo arrastrado en el registro de control y deposita el residuo de vuelta, optimizando el uso de los registros de la CPU.

La demostración de la cota del acarreo provista permitira mostrar como de ella depende la seguridad de que el tipo de datos ULONG jamás experimente un desbordamiento destructivo oculto durante la ejecución del bucle central:

• El algoritmo se compone de dos bucles lógicos con roles de indexación asimétricos:
  • Bucle Externo (Controlado por 'i'): Gobierna el recorrido secuencial de los dígitos del multiplicando \(a\). Se encarga de reinicializar los estados de acarreo al arrancar cada fila y de consolidar el acarreo residual final de la fila en la posición de memoria de peso alto \(p_{i+n}\).
  • Bucle Interno (Controlado por 'j'): Modula el cálculo continuo de los productos internos cruzados \(a_i \cdot b_j\) para todos los dígitos del multiplicador \(b\). Su frecuencia de ejecución total es un reflejo exacto del producto de las longitudes lógicas de los operandos (\(m \cdot n\)).

• El pseudocódigo matemático del paso 4 define explícitamente el uso de una variable temporal amplia \(t\) para acumular la suma local y extraer tanto el residuo modular como el nuevo acarreo por división entera (\(c \leftarrow \lfloor t / B \rfloor\)).
• El Enfoque de Compresión: Siguiendo la arquitectura implementada en la función de adición de la página 25, la función criptográfica real en C prescinde del uso explícito de una variable llamada t.
• En su lugar, el producto cruzado de tipo ULONG y la inyección del acarreo previo se compactan en una única expresión compuesta lineal, donde la variable del acarreo local (carry) absorbe simultáneamente la suma temporal y redistribuye los bits mediante operaciones de desplazamiento lógico, optimizando el uso de los registros internos de la CPU.

• El paso 1 del algoritmo teórico exige realizar un barrido lineal para inicializar todo el arreglo de destino a cero de forma secuencial (\(p_i \leftarrow 0\)).
• El autor advierte que, para el código fuente de producción en C, se optará por un procedimiento de inicialización significativamente más eficiente. En lugar de limpiar forzadamente todo el búfer máximo, se aplicará un formateo selectivo o se delegará la limpieza a la fase de copia inicial no destructiva para ahorrar ciclos de reloj en el hot-path del procesador.

"Analogously to how we proceeded in the case of addition, the inner products t are thus represented as ULONG types. The variable t is nonetheless not used explicitly, and the setting of the result digits p_i+j and the carry c occurs rather within a single expression, analogous to the process already mentioned in connection with the addition function (see page 25)." – Página 36

La homogeneidad estilística y estructural de Robert Hammelrath en toda la biblioteca. Justifica matemáticamente la ausencia de variables intermedias redundantes en la pila, forzando la canalización de bits directamente sobre los registros de hardware.

Es entonces cuando la optimización no se limita a usar un tipo ancho de 64 bits (ULONG) parte de esto radica en evitar el costo de almacenamiento de escrituras temporales en memoria. Al fusionar la asignación del residuo del dígito y el cálculo del acarreo en una sola línea de código compuesta, se le permite al optimizador de GCC generar instrucciones vectorizadas nativas directamente en el microprocesador.

"Function: multiplication Syntax: int mul_l (CLINT f1_l, CLINT f2_l, CLINT pp_l); Input: f1_l, f2_l (factors) Output: pp_l (product) Return: E_CLINTOK if all is ok, E_CLINTOFL if overflow" – Página 36

El contrato de software de la API para la operación de multiplicación. Define de manera estricta los nombres de las variables de cabecera y las constantes de error que el hilo de ejecución superior debe evaluar.

Esto es importante ya que, explica los límites de la función de multiplicación estándar que recibe dos factores por referencia (f1_l y f2_l) y deposita el resultado multiprecisión en pp_l. El retorno está rígidamente condicionado: si la longitud combinada del producto rompe la frontera de almacenamiento física asignada, el estado muta de forma defensiva a E_CLINT_OFL.

El procedimiento matemático para computar el producto \(p = a \cdot b\) opera formalmente de la siguiente manera:

1. Paso 1: Inicializar el arreglo acumulador a cero: \(p_i \leftarrow 0\) para todo \(i = 0, \dots, m + n - 1\).
2. Paso 2: Inicializar el contador del ciclo externo del multiplicando: \(i \leftarrow 0\).
3. Paso 3: Inicializar el contador del ciclo interno del multiplicador y el registro de acarreo: \(j \leftarrow 0\) y \(c \leftarrow 0\).
4. Paso 4: Calcular la adición multiprecisión de la columna y el producto cruzado: \(t \leftarrow p_{i+j} + a_i b_j + c\). Actualizar la celda destino aplicando módulo \(p_{i+j} \leftarrow t \pmod B\) y calcular el acarreo mediante división entera \(c \leftarrow \lfloor t / B \rfloor\).
5. Paso 5: Incrementar \(j \leftarrow j + 1\). Si \(j \leq n - 1\), saltar y repetir desde el Paso 4 para agotar la fila del multiplicador.
6. Paso 6: Guardar el acarreo residual de la fila actual en el extremo superior de la columna: \(p_{i+n} \leftarrow c\).
7. Paso 7: Incrementar \(i \leftarrow i + 1\). Si \(i \leq m - 1\), saltar y reiniciar una nueva fila desde el Paso 3.
8. Paso 8: Retornar el vector normalizado compacto de salida: \(p = (p_{m+n-1}p_{m+n-2}\dots p_0)_B\).

Las trazas de terminal recolectadas en el toolchain nativo de Gentoo Linux confirman el paso exitoso de la refactorización a través de los tres filtros de compilación y su ejecución síncrona predecible:

[GENTOO-SYS] Inicializando ejecucion de mul_l de la pagina 37
[GENTOO-SYS] Estado inicial de ejecucion de la multiplicacion: 0

• En lugar de realizar un barrido lineal costoso para rellenar con ceros todo el arreglo de doble longitud p_l, el algoritmo aplica un truco arquitectónico de rendimiento para salvar tiempo de CPU.
• El sistema calcula el primer producto parcial de forma aislada, multiplicando el primer dígito del multiplicando (a_l[1]) por la cadena completa del multiplicador (b_l). Los residuos de esta operación se escriben de forma secuencial y destructiva directamente sobre p_l, actuando de facto como el formateo e inicialización encubierta del arreglo destino.

• Justo después del cálculo inicial, arranca el bucle anidado que procesa el resto de los dígitos del multiplicando (a_l), comenzando estrictamente desde su segundo elemento (a_l[2]).
• El Bucle Externo (Controlado por 'csptr_l'): Modula el desplazamiento de la fila del producto parcial. Inicializa el puntero de escritura basándose en la posición actual de lectura del multiplicando, asegurando el escalado exponencial correcto (\(B^{i+j}\)).
• El Bucle Interno (Controlado por 'bptr_l'): Recorre cíclicamente los componentes del multiplicador (b_l). Ejecuta la expresión compacta de Robert Hammelrath sumando el producto intermedio escalar (av * *bptr_l) al valor ya residente en la celda destino (*pptr_l), arrastrando e inyectando la variable de control carry de 64 bits de forma contigua.

• Al finalizar la fase aritmética, la longitud lógica combinada máxima posible del producto se establece inicialmente como la suma directa de las longitudes individuales de ambos factores mediante SETDIGITS_L (p_l, DIGITS_L (a_l) + DIGITS_L (b_l)).
• Dado que la multiplicación real puede dar un número con un dígito de peso alto exactamente en cero, se invoca de forma mandatoria la macro de bajo nivel RMLDZRS_L(p_l) para inspeccionar vectorialmente el arreglo y podar los ceros a la izquierda excedentes, ajustando el tamaño real canónico de la estructura.

"To save time in the computation, instead of the initialization required above, the partial product (b_n-1b_n-2… b₀)_B ⋅ a₀ is calculated in a loop and stored in p_n, p_n-1, … p₀." – Página 38

Esta premisa de diseño criptográfico fundamenta la desviación del código real frente al pseudocódigo puramente teórico del Algoritmo M de Knuth (que exigía rellenar todo con ceros en el paso 1). Explica cómo reducir a la mitad las operaciones de escritura en memoria del búfer destino.

Inicializar un arreglo de doble longitud con ceros para luego sobrescribirlo inmediatamente con sumas parciales es un desperdicio de ciclos de reloj. La biblioteca optimiza esto inyectando la multiplicación del primer dígito de forma directa como una operación de escritura limpia en la pila, dejando el búfer listo y pre-inicializado para las sumas acumulativas de los siguientes bucles.

"Next follows the nested multiplication loop, beginning with the digit a_l[2] of a_l." – Página 38

La sincronización exacta de los contadores e índices físicos de los punteros de la memoria de la pila. Evita que el algoritmo compute dos veces el primer dígito del multiplicando, manteniendo la precisión matemática del producto.

El punto de partida del bucle externo. Como el elemento a_l[1] (el dígito menos significativo) ya fue consumido por completo en la fase de inicialización y optimización previa, el bucle incremental de punteros aptr_l avanza una palabra en la memoria para procesar de manera exclusiva desde la segunda posición del arreglo multiprecisión hacia arriba.

"The largest possible length of the result is the sum of the numbers of digits of a_l and b_l. If the result has one digit fewer, this is determined by the macro RMLDZRS_L." – Página 38

Establece el principio algebraico que rige el dimensionamiento de la salida y justifica la inyección de la macro de poda justo al cerrarse las operaciones de punteros de hardware.

Detalla que la cota superior del tamaño de un producto de enteros grandes es estrictamente \(m+n\). No obstante, matemáticamente el dígito de mayor peso puede colapsar a cero. La cita explica que la biblioteca asume inicialmente la cota máxima en la cabecera lógica y delega de forma inmediata a RMLDZRS_L la tarea de escanear y recortar la estructura si el número resultó ser de un orden de magnitud menor.

• Al finalizar el cálculo de los bucles anidados de la seccion anterior, el sistema evalúa si la longitud lógica del producto temporal p_l ha superado el límite físico rígido de la biblioteca mediante if (DIGITS_L (p_l) > (USHORT)CLINTMAXDIGIT).
• Si se detecta una saturación por exceso de bits (overflow), la biblioteca ejecuta una mitigación proactiva invocando ANDMAX_L(p_l) para forzar una reducción matemática bajo el módulo \((N_{max} + 1)\), truncando los componentes excedentes inseguros. El flag de control muta a E_CLINT_OFL antes de transferir los datos limpios al destino final pp_l vía cpy_l().

• El texto formaliza la complejidad del hot-path de la multiplicación general como cuadrática, denotada por \(O(m \cdot n)\), siendo directamente proporcional al producto del número de dígitos de ambos operandos.
• Como optimización, se introduce la función de multiplicación mixta umul_l(). Cuando uno de los factores es un escalar nativo de 16 bits (USHORT), la longitud del segundo operando es fijada de manera constante en \(n=1\). Esto colapsa la ecuación de complejidad a un escenario estrictamente lineal: \[O(m)\]
• Esta reducción drástica de instrucciones no se debe a un refinamiento algebraico avanzado (como Karatsuba o FFT), sino a la explotación de la brevedad del argumento de hardware, convirtiéndose en una pieza fundamental para rutinas de capas superiores como la exponenciación modular con bases cortas (wmexp_l()).

• La arquitectura de umul_l() se diseña bajo un principio estricto de reutilización de software. En lugar de instanciar un algoritmo completamente nuevo, el sistema extrae e integra un segmento lógico idéntico extraído directamente del cuerpo caliente de mul_l() con sutiles modificaciones para omitir el bucle exterior redundante.
• El epílogo de declaraciones de la función reserva espacio en la pila para variables locales cualificadas como register para maximizar la velocidad de desreferenciación de punteros, y define un búfer temporal de acumulación p_l acotado.

"if (DIGITS_L (p_l) > (USHORT)CLINTMAXDIGIT) * overflow ? * { ANDMAX_L (p_l); * reduce modulo (Nmax + 1) * OFL = E_CLINTOFL; }" – Página 39

Esta sección del código es vital porque ilustra el punto exacto de interrupción y contención de desbordamientos de la multiplicación criptográfica. Documenta la bifurcación defensiva final de la rutina antes de exponer el resultado al llamador.

La biblioteca no permite que un desbordamiento de bits corrompa posiciones adyacentes de la memoria de la pila. Si el crecimiento combinado de los factores violó el umbral seguro (CLINTMAXDIGIT), la función aplica una reducción forzada mediante aritmética de anillos modulares y altera el estado de retorno a E_CLINT_OFL para notificar el fallo de capacidad.

"This short version of CLINT multiplication requires O(n) CPU multiplications, which is the result not of any particular refinement of the algorithm, but of the shortness of the USHORT argument." – Página 39

La justificación de rendimiento y eficiencia matemática de la API mixta frente a las rutinas multiprecisión binarias completas, fundamentando su uso en operaciones repetitivas de alto costo como la exponenciación.

La ganancia de velocidad de la función con prefijo "u" no proviene de una técnica exótica de división y conquista. El colapso de la complejidad de cuadrática a lineal es una consecuencia directa de sustituir una estructura vectorial por un escalar nativo, lo que permite eliminar el bucle de control externo y realizar el cálculo en una única pasada lineal por el procesador.

"Function: multiplication of a CLINT type by a USHORT Syntax: int umul_l (CLINT aa_l, USHORT b, CLINT pp_l);" – Página 39

Establece el contrato de software y las restricciones de tipado obligatorias para invocar la multiplicación mixta de forma segura dentro de la biblioteca.

Esto es importante porque define de forma explícita que el orden de los operandos es asimétrico y rígido: el multiplicando siempre es el entero grande multiprecisión (aa_l) pasado por referencia, mientras que el multiplicador es el escalar puro (b) pasado por valor directo de 16 bits. El producto final se deposita de manera no destructiva en la dirección de pp_l.

• Tras los preliminares de la página anterior, el factor CLINT se multiplica en una única pasada lineal a través de un bucle controlado por el puntero aptr_l.
• La expresión interna multiplica el escalar b (USHORT) por el dígito actual *aptr_l, promoviendo ambos a 64 bits (ULONG). A este producto se le inyecta el acarreo de la iteración previa extraído mediante un desplazamiento lógico: (ULONG)(USHORT)(carry >> BITPERDIGIT).
• El resultado se trunca a 16 bits y se escribe directamente en la celda destino *pptr_l++, avanzando los punteros de lectura y escritura de forma síncrona.

• Al agotarse el multiplicando (aptr_l > msdptra_l), el acarreo residual que permanece en vuelo en la variable carry se extrae mediante un desplazamiento y se escribe físicamente en el extremo superior de la estructura: *pptr_l = (USHORT)(carry >> BITPERDIGIT).
• Se asume inicialmente una expansión de tamaño incrementando en uno la cabecera lógica del búfer destino mediante SETDIGITS_L (p_l, DIGITS_L (a_l) + 1).
• Inmediatamente después, la macro RMLDZRS_L(p_l) realiza un barrido vectorial inverso para podar los ceros a la izquierda excedentes en caso de que el acarreo final haya sido nulo, normalizando la estructura a su tamaño canónico real. El cierre valida los límites físicos contra CLINTMAXDIGIT y aplica reducción por módulo si ocurre un desbordamiento.

• El libro introduce la optimización del cálculo de un cuadrado (\(a^2\)). Multiplicar un número por sí mismo requiere significativamente menos operaciones que multiplicar dos números independientes de igual longitud.
• Esta ganancia de velocidad es una consecuencia directa de la simetría algebraica de la matriz de productos parciales cuando los operandos son idénticos (\(a_i \cdot a_j = a_j \cdot a_i\)).
• Debido a que algoritmos criptográficos como la exponenciación modular ejecutan cientos de cuadrados consecutivos, diseñar una función específica para cuadrados permite un ahorro masivo de ciclos de reloj en el procesador.

"and at the end the carry is stored in the most-significant USHORT digit of the CLINT value." – Página 40

La justificación aritmética para la línea de asignación que se ejecuta inmediatamente al salir del bucle. Garantiza que el remanente matemático no se pierda al romperse el ciclo lineal de control de dígitos.

El bucle se detiene cuando ya no hay más dígitos que leer en el multiplicando, pero la variable carry aún puede contener un residuo neto. Al igual que en la suma clásica de papel, este último bit se deposita de manera forzada en la celda de peso alto contigua (*pptr_l), completando la expansión física del número.

"This observation is very important, since when it comes to exponentiation, which involves not one, but hundreds, of squarings, we shall be able to achieve considerable savings in speed." – Página 40

Provee la justificación de rendimiento de ingeniería de software para desarrollar una función de cuadrados dedicada (squ_l) en lugar de reutilizar de manera perezosa la función de multiplicación estándar mul_l(a, a, de).

La optimización no busca acelerar una instrucción aislada. En protocolos de cifrado como RSA, la exponenciación modular se compone de secuencias masivas de multiplicaciones elevadas al cuadrado. Aprovechar la simetría de los productos cruzados para eliminar la mitad de las multiplicaciones elementales de hardware acelera de forma dramática el rendimiento total del microprocesador.

• La Figura 4-2 ilustra la mecánica de calcular \((a_2a_1a_0)_B \cdot (a_2a_1a_0)_B\). En ella se observa que los productos internos \(a_i \cdot a_j\) para elementos idénticos donde \(i = j\) ocurren exactamente una vez (resaltados en negrita).
• Por el contrario, los productos cruzados donde \(i \neq j\) (encerrados en cajas en la figura) aparecen exactamente dos veces debido a la propiedad conmutativa (\(a_i a_j = a_j a_i\)).

• Esta simetría permite reescribir la sumatoria del producto acumulado en tres componentes algebraicos:

  \[p = \sum_{i,j=0}^{n-1} a_i a_j B^{i+j} = 2 \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} a_i a_j B^{i+j} + \sum_{j=0}^{n-1} a_j^2 B^{2j}\]

• Impacto Computacional: El número de multiplicaciones elementales obligatorias en hardware se reduce drásticamente desde un comportamiento puramente cuadrático de \(n^2\) (método escolar estándar) hacia una cota optimizada de:

  \[\frac{n(n + 1)}{2}\]

  

• La representación algorítmica natural traduce la fórmula matemática en una estructura de dos bucles anidados que procesa las sumas en paralelo:
  • Inicialización e Índices de Fila: Los pasos 1 y 2 ponen a cero el búfer destino (\(p_i \leftarrow 0\)) e inicializan el contador externo \(i \leftarrow 0\).
  • Paso de la Diagonal Principal: El paso 3 computa el cuadrado puro del dígito de la diagonal mediante \(t \leftarrow p_{2i} + a_i^2\), aislando el residuo modular y el acarreo \(c \leftarrow \lfloor t / B \rfloor\).
  • El Bucle de Productos Duplicados: Los pasos 5 y 6 ejecutan el ciclo interno indexado por \(j\) (desde \(i+1\) hasta \(n-1\)). Multiplica el producto intermedio cruzado por dos y le inyecta el residuo previo: \(t \leftarrow p_{i+j} + 2a_i a_j + c\), propagando \(c \leftarrow \lfloor t / B \rfloor\).
  • Cierre de Fila: Los pasos 7 y 8 depositan el acarreo en \(p_{i+n}\) e incrementan el ciclo externo hasta agotar los \(n-1\) dígitos.

• Al multiplicar un producto cruzado por dos e incorporar el residuo residente y el acarreo anterior, el valor de la variable temporal \(t\) en el paso 5 experimenta una expansión severa.
• El autor demuestra que el peor escenario teórico de saturación de bits puede alcanzar un valor máximo de: \[2B^2 - 2B\]
• Esta cota aritmética implica un cambio de diseño de software fundamental: el valor supera la barrera tradicional de \(B^2 - 1\). Por lo tanto, para representar \(t\) de forma segura sin provocar truncamientos destructivos en la memoria de la pila, se requiere obligatoriamente una palabra de hardware que abarque más de dos dígitos en base \(B\). Dado que en Gentoo Linux \(B = 2^{16}\), un registro ULONG de 64 bits ofrece la holgura perfecta para contener los 33 bits necesarios para \(2B^2 - 2B\).

"The number of required elementary multiplications is thus reduced with respect to the school method from n² to n(n + 1)/2." – Página 41

La justificación matemática y económica de por qué la biblioteca implementa una función dedicada a calcular cuadrados (squ_l). Documenta cuantitativamente el ahorro de instrucciones para el procesador.

Para un entero grande criptográfico con \(n = 3\) dígitos, el método escolar requiere \(3^2 = 9\) multiplicaciones en el hot-path. Al explotar la simetría matricial, el nuevo algoritmo reduce este número a \(\frac{3(4)}{2} = 6\) multiplicaciones elementales, eliminando un 33% del tiempo de cómputo del microprocesador. Para claves RSA grandes, este ahorro mitiga drásticamente la latencia de cifrado.

EGIN_QUOTE "In selecting the necessary data types for the representation of the variables we must note that t can assume the value (B - 1) + 2(B - 1)² + (B - 1) = 2B² - 2B (in step 5 of the algorithm). But this means that for representing t to base B more than two digits to base B will be needed…" – Página 41 #+END_QUOTE

La restricción física de hardware obligatoria para el tipado de variables del bucle interno de cuadrados. Alerta al programador de que la lógica de la adición o multiplicación estándar no es aplicable directamente aquí debido al factor multiplicativo \(2a_i a_j\).

Es entonces que en el peor escenario de la celda (\(p_{i+j} = B-1\), \(a_i=B-1\), \(a_j=B-1\), \(c=B-1\)), la expresión computa \((B-1) + 2(B^2 - 2B + 1) + (B-1) = 2B^2 - 2B\). Como este valor supera el límite de un entero de doble palabra tradicional (\(B^2\)), el lenguaje C requiere una variable extendida para que el acarreo \(c\) no colapse de forma destructiva antes de la división entera.

La optimización e implementación en C de un algoritmo para elevar números de precisión arbitraria al cuadrado (big numbers / multiprecision squaring).

En lenguajes de bajo nivel o ensamblador, es sencillo acceder directamente al bit de acarreo (carry bit) del procesador cuando una multiplicación genera un desbordamiento. Sin embargo, en C estándar no existe un acceso directo y portable a este registro de acarreo del hardware. Si se intenta realizar la multiplicación por 2 (shift left) en el mismo paso que la acumulación de productos parciales de dígitos cruzados, el resultado temporal \(t\) puede sobrepasar el límite máximo almacenable en una variable de tipo entero nativo como ULONG (\(2B^2 - 1\)).

Para resolver esta limitación sin recurrir a tipos de datos más grandes o a ensamblador inline, el algoritmo se reestructura dividiendo el proceso en fases o bucles independientes:

1. Cálculo de productos cruzados no diagonales: Se acumulan los productos \(a_i a_j\) para \(i \neq j\).
2. Duplicación: Se realiza un bucle exclusivo para multiplicar todo el resultado acumulado por 2 (desplazamiento para considerar los términos mixtos del binomio).
3. Suma de los términos cuadrados: Se suman los términos de la diagonal \(a_i^2\) en las posiciones correspondientes.

A costa de un mínimo sobrecosto (overhead) en la gestión de bucles, esta reestructuración evita la necesidad de bits de acarreo adicionales y garantiza que todas las variables permanezcan dentro de los límites nativos del tipo ULONG.

"While this poses no problem for an assembler implementation, in which one has access to the carry bit of the CPU, it is difficult in C to handle the additional carry digit. To get around this dilemma, we alter the algorithm in such a way that in step 5 the required multiplication by 2 is carried out in a separate loop." (pag. 42)

Al calcular \((a_0 + a_1 B + \dots)^2\), los productos de términos diferentes \(a_i a_j\) aparecen dos veces (\(2 a_i a_j\)). Si se multiplica por 2 al mismo tiempo que se calcula \(a_i a_j + c\), la suma intermediate \(t = 2 a_i a_j + p_{i+j} + c\) puede exceder la capacidad máxima del tipo de dato de precisión base (por ejemplo, ULONG).

En ensamblador se puede verificar la bandera de acarreo (CPU carry flag) de la ALU tras una suma o rotación. En C estándar, detectar desbordamientos de enteros requiere comprobaciones adicionales condicionales que degradan el rendimiento.

Separar la multiplicación por 2 en un bucle independiente posterior. Al procesar \(a_i a_j\) sin el factor 2, los valores intermediarios caben en el tipo ULONG sin riesgo de overflow.

"Algorithm 2 for squaring

1. Initialization: Set \(p_i \leftarrow 0\) for \(i = 0, \ldots, n - 1\).
2. Calculate the product of digits of unequal index: Set \(i \leftarrow 0\).

…

1. Multiplication of inner products by 2: Set \(i \leftarrow 1\) and \(c \leftarrow 0\).

…

1. Addition of the inner squares: Set \(i \leftarrow 0\) and \(c \leftarrow 0\)."

• Fase de Productos Cruzados (Pasos 1-7): Computa \(p_{i+j} \leftarrow p_{i+j} + a_i a_j\) únicamente para los pares con \(i < j\). Esto reduce a la mitad el número de multiplicaciones de gran tamaño necesarias en comparación con una multiplicación general (\(n(n-1)/2\) en lugar de \(n^2\)).
• Fase de Duplicación (Pasos 8-11): Multiplica el resultado acumulado en los pasos anteriores por 2 mediante un bucle simple que propaga el acarreo \(c\) dígito por dígito.
• Fase de Cuadrados Diagonales (Pasos 12-16): Añade los términos \(a_i^2\) a las posiciones pares \(p_{2i}\) y propaga el acarreo a \(p_{2i+1}\). Esta descomposición optimiza el rendimiento general en sistemas criptográficos (RSA, ECC), donde la elevación al cuadrado es una operación frecuente.

"In the C function for squaring the initialization in step 1 is likewise, in analogy to multiplication, replaced by the calculation and storing of the first partial product \(a_0 (a_{n-1} a_{n-2} \cdots a_1)_B\)."

En lugar de asignar manualmente \(0\) a todas las posiciones de memoria del arreglo \(p\) (Paso 1) y luego sumar los productos parciales sobre \(0\), la implementación real en C fusiona la inicialización con el cálculo de la primera fila de productos parciales.

Al almacenar directamente \(a_0 \times (a_{n-1} \dots a_1)_B\) en la primera pasada, se evitan escrituras innecesarias en la RAM o caché, optimizando el rendimiento de operaciones criptográficas de alto impacto donde la velocidad de cómputo es crítica.

La primera parte de la implementación en C de la función sqr_l(), cuya finalidad es calcular el cuadrado de un entero de gran tamaño representado en la estructura CLINT.

El código expone la estructura de control inicial de la función: declaración de variables locales y punteros de registros optimizados, gestión de excepciones (como el caso en que el número a elevar al cuadrado sea cero) y el inicio de la primera fase del algoritmo de elevación al cuadrado.

En lugar de ejecutar un bucle previo para limpiar la memoria escribiendo ceros en todo el arreglo resultado \(p\), la función aprovecha la primera pasada del cálculo parcial \(a_0 (a_{n-1} a_{n-2} \dots a_1)_B\) para escribir directamente los datos iniciales en la memoria. Como esta multiplicación involucra términos a partir de la posición \(p_1\), la función asigna de forma manual y explícita el valor \(0\) al dígito menos significativo \(p_0\) antes de arrancar el bucle principal.

"Function: squaring Syntax: int sqr_l (CLINT f_l, CLINT pp_l); Input: f₁ (factor) Output: pp_l (square) Return: E_CLINTOK if all is ok E_CLINTOFL if overflow"

sqr_l recibe como parámetros de entrada/salida referencias de tipo CLINT. f_l actúa como el operando base a elevar al cuadrado (\(f\)), mientras que pp_l almacena el producto final (\(f^2\)).

Devuelve un entero representando el estado del cómputo. La constante E_CLINT_OK indica que la operación concluyó sin anomalías, mientras que E_CLINT_OFL actúa como un guardián de seguridad que notifica si el número resultante excede la cantidad máxima de dígitos permitidos por la arquitectura del tipo CLINT.

"cpy_l (a_l, f_l); if (EQZ_L (a_l)) { SETZERO_L (pp_l); return E_CLINTOK; } msdptrb_l = MSDPTR_L (a_l); msdptra_l = msdptrb_l - 1;"

En primer lugar, se copia el operando a una variable local a_l con cpy_l para evitar modificar el argumento original. Luego, EQZ_L comprueba si la variable es igual a cero (\(0^2 = 0\)). Si es el caso, asigna cero a pp_l mediante SETZERO_L e interrumpe la función de forma inmediata, ahorrando ciclos de procesador.

MSDPTR_L calcula la dirección en memoria del dígito más significativo (Most Significant Digit). msdptrb_l apunta al final absoluto del número (dígito \(n-1\)), mientras que msdptra_l se posiciona en \(n-2\). Estos límites definen las fronteras exactas que gobernarán la iteración de los productos cruzados.

"The initialization of the result vector addressed by pptr_l is carried out by means of the partial product \(a_0 (a_{n-1}a_{n-2} \dots a_1)_B\), in analogy with multiplication. The digit \(p_0\) is here not assigned; it must be set to zero."

Cuando multiplicamos el primer dígito \(a_0\) por el resto del número \((a_{n-1} \dots a_1)_B\), estamos calculando términos que pertenecen a las posiciones de peso \(B^1, B^2, \dots, B^n\). El término correspondiente a \(B^0\) (es decir, \(p_0\)) no recibe ningún aporte durante este paso, ya que el término diagonal \(a_0^2\) se sumará en una etapa posterior.

Asignar `*LSDPTR<sub>L</sub> (p<sub>1</sub>) = 0;` en C fuerza explícitamente a que el primer dígito (Least Significant Digit) valga cero. Esto sustituye una operación costosa de limpieza de memoria (como `memset(p, 0, sizeof(p))`) por una inicialización "al vuelo" a medida que se calculan y escriben los primeros productos parciales en el vector de salida.

Esta sección abarca el núcleo del Algoritmo 2 para elevar al cuadrado en C (página 62). En ella se completan las tres fases fundamentales del algoritmo de precisión arbitraria:

1. Acumulación de productos cruzados (\(a_i a_j\) con \(i < j\)): Mediante bucles anidados se computan y acumulan los productos parciales de dígitos no diagonales. El avance del puntero de destino (`csptr<sub>l</sub> += 2`) garantiza que cada nueva fila de productos parciales se sume con el desplazamiento posicional correcto en potencias de la base \(B\).
2. *Duplicación del resultado intermedio mediante desplazamiento de bits (*shift left):** Una vez calculados los productos de índices desiguales, se realiza un recorrido lineal sobre todo el vector intermedio \(p\) multiplicando cada dígito por 2 (`<< 1`) y propagando el acarreo (carry). Esto toma el lugar de computar \(a_i a_j\) dos veces, reduciendo drásticamente las multiplicaciones de hardware.
3. Inicio del cómputo de la diagonal principal (\(a_i^2\)): Se prepara la fase final donde se agregan los cuadrados directos de cada dígito individual a las posiciones de peso par del resultado.

Toda la aritmética se apoya en casting explícito a ULONG para capturar el desbordamiento de 32/64 bits, extrayendo el nuevo acarreo mediante desplazamientos hacia la derecha (carry >> BITPERDGT).

"The loop for summing the inner products \(a_i a_j\).

for (aptr_l = LSDPTR_L (a_l) + 1, csptr_l = LSDPTR_L (p_l) + 3; aptr_l <= msdptra_l; aptr_l++, csptr_l = 2) { carry = 0; av = *aptr_l; for (bptr_l = aptr_l + 1, pptr_l = csptr_l; bptr_l <= msdptrb_l; bptr_l+, pptr_l++) { *pptr_l = (USHORT)(carry = (ULONG)av * (ULONG)*bptr_l + (ULONG)*pptr_l + (ULONG)(USHORT)(carry >> BITPERDGT)); } *pptr_l = (USHORT)(carry >> BITPERDGT); } msdptrc_l = pptr_l;"

El puntero base de la columna de salida `csptr<sub>l</sub>` avanza 2 posiciones por cada iteración del bucle exterior. Esto responde a la propiedad matemática de la base \(B\): al incrementar el índice del dígito multiplicador \(a_i\) (\(i \ge 1\)), la posición del primer producto parcial en la suma acumulada debe desplazarse en \(B^{2i+1}\).

Dentro del bucle interno, `(ULONG)av * (ULONG)*bptr<sub>l</sub> + (ULONG)*pptr<sub>l</sub>` realiza la multiplicación y acumula el valor previo que ya existía en la posición de memoria `*pptr<sub>l</sub>`.

La parte baja se almacena en el arreglo tras hacer cast a USHORT, mientras que los bits superiores (el acarreo) se desplazan mediante `carry >> BITPERDGT` (donde `BITPERDGT` es típicamente 16 bits) para ser sumados en la siguiente iteración de `pptr<sub>l</sub>++`.

Al finalizar la acumulación, se guarda la posición final del puntero en `msdptrc<sub>l</sub> = pptr<sub>l</sub>`, fijando el límite superior exacto para la siguiente fase de duplicación.

"Then comes multiplication of the intermediate result in pptr_l by 2 via shift operations (see also Section 7.1).

carry = 0; for (pptr_l = LSDPTR_L (p_l); pptr_l <= msdptrc_l; pptr_l++) { *pptr_l = (USHORT)(carry = (((ULONG)*pptr_l) << 1) + (ULONG)(USHORT)(carry >> BITPERDGT)); } *pptr_l = (USHORT)(carry >> BITPERDGT);"

En el desarrollo del cuadrado de un polinomio \((a_0 + a_1 B + \dots)^2\), los términos mixtos \(a_i a_j\) (con \(i \neq j\)) aparecen dos veces (\(2 a_i a_j\)). En lugar de multiplicarlos individualmente por 2 dentro del bucle de acumulación —lo que exigiría variables temporales más grandes o gestionar un bit de acarreo no nativo en C—, el algoritmo acumula primero \(\sum a_i a_j\) y luego duplica todo el vector en una única pasada lineal.

Multiplicar cada palabra de 16 bits por 2 equivale a desplazar sus bits un lugar a la izquierda (`((ULONG)*pptr<sub>l</sub>) << 1`).

Si la duplicación excede la capacidad del dígito nativo (más de \(2^{16}-1\)), el bit sobrante pasa a formar parte de `carry`, sumándose en la iteración contigua mediante `(ULONG)(USHORT)(carry >> BITPERDGT)`.

"Now we compute the “main diagonal.”

carry = 0; for (bptr_l = LSDPTR_L (a_l), pptr_l = LSDPTR_L (p_l); bptr_l <= msdptrb_l; bptr_l++, pptr_l++)"

Tras duplicar los términos mixtos, solo resta calcular la contribución de los términos diagonales \(a_i^2 \cdot B^{2i}\).

Se reinicia `carry = 0` y se alinean simultáneamente el puntero de lectura de operandos `bptr<sub>l</sub>` (que lee \(a_0, a_1, \dots\)) con el puntero de escritura de resultados `pptr<sub>l</sub>`.

Esta separación en 3 fases garantiza que el código ejecute el número mínimo posible de multiplicaciones por hardware en el procesador, aprovechando al máximo la jerarquía de memoria y la ejecución fuera de orden (out-of-order execution) de las CPUs modernas.

En la primera parte, se completa el cálculo de la diagonal principal acumulando los términos \(a_i^2\) y gestionando la propagación final del acarreo. Posteriormente, se ajusta el recuento total de dígitos del resultado (\(2n\)) y se elimina cualquier cero no significativo a la izquierda mediante RMLDZRS_L. Se incluye un mecanismo de control de fronteras que verifica si el resultado excede el tamaño máximo permitido (CLINTMAXDIGIT); de ser así, el número se reduce módulo \((N_{max} + 1)\) y se retorna el código de advertencia E_CLINT_OFL.

La motivación del Algoritmo de Karatsuba. Aunque la elevación al cuadrado reduce el número de multiplicaciones elementales a \(\frac{n(n+1)}{2}\) (siendo el doble de rápida que la multiplicación tradicional), su complejidad sigue siendo cuadrática \(O(n^2)\). Karatsuba propone una estrategia de "divide y vencerás" que descompone números de \(2k\) dígitos en bloques de tamaño \(k\), abriendo paso a una reducción teórica de la complejidad computacional.

" *pptr_l = (USHORT)(carry = (ULONG)*bptr_l * (ULONG)*bptr_l + (ULONG)*pptr_l + (ULONG)(USHORT)(carry >> BITPERDGT)); pptr_l++; *pptr_l = (USHORT)(carry = (ULONG)*pptr_l + (carry >> BITPERDGT));"

En la primera instrucción se calcula el término diagonal \(a_i^2 = \text{*bptr\_l} \times \text{*bptr\_l}\), acumulando tanto el valor previo del vector resultado `*pptr<sub>l</sub>` como el acarreo pendiente de la posición anterior.

Inmediatamente después de escribir el dígito de menor peso, se avanza el puntero de destino (`pptr<sub>l</sub>++`) y se suma el acarreo resultante a la posición \(p_{2i+1}\). Esto garantiza que cada término diagonal \(a_i^2\) impacte directamente en el par de posiciones \(B^{2i}\) y \(B^{2i+1}\).

"SETDIGITS_L (p_l, DIGITS_L (a_l) << 1); RMLDZRS_L (p_l);

if (DIGITS_L (p_l) > (USHORT)CLINTMAXDIGIT) * overflow ? * { ANDMAX_L (p_l); * reduce modulo (Nmax + 1) * OFL = E_CLINTOFL; } cpy_l (pp_l, p_l); return OFL;"

Elevar un entero de \(n\) dígitos al cuadrado produce un resultado de como máximo \(2n\) dígitos. La macro `SETDIGITS<sub>L</sub>` actualiza el encabezado del tipo CLINT desplazando la cantidad de dígitos de \(a_l\) un bit a la izquierda (equivalente a multiplicar por 2).

Elimina los ceros principales sobrantes en caso de que \(a^2\) ocupe \(2n - 1\) dígitos en lugar de \(2n\).

Si el número de dígitos excede la constante CLINTMAXDIGIT, la macro ANDMAX_L trunca el resultado aplicando una máscara binaria para reducirlo módulo \((N_{max} + 1)\), registrando el estado de desbordamiento en OFL = E_CLINT_OFL.

"The run time for squaring is, with \(O(n^2)\), likewise quadratic in the number of digits of the operators, but with \(n(n + 1)/2\) elementary multiplications it is about twice as fast as multiplication."

Ambas operaciones pertenecen a la clase de complejidad \(O(n^2)\). Sin embargo, la multiplicación estándar de dos números distintos requiere \(n^2\) multiplicaciones de palabras simples, mientras que la elevación al cuadrado optimizada solo requiere \(\frac{n(n+1)}{2}\).

En algoritmos criptográficos como RSA o Diffie-Hellman (que ejecutan cientos de exponenciaciones modulares mediante el método Square-and-Multiply), esta reducción del \(50\%\) en multiplicaciones representa una aceleración masiva en el tiempo total de cómputo.

"We assume that \(a\) and \(b\) are natural numbers with \(n = 2k\) digits to base \(B\), so that we can write \(a = (a_1 a_0)_{B^k}\) and \(b = (b_1 b_0)_{B^k}\)… \[ab = B^{2k} a_1 b_1 + B^k (a_0 b_1 + a_1 b_0) + a_0 b_0\]"

Para multiplicar números grandes, Karatsuba divide cada entero de \(n = 2k\) dígitos en dos mitades de \(k\) dígitos: una parte de alto peso (\(a_1, b_1\)) y una de bajo peso (\(a_0, b_0\)), representadas como \(a = a_1 B^k + a_0\) y \(b = b_1 B^k + b_0\).

La expansión directa del producto requiere evaluar 4 multiplicaciones de tamaño \(k\): \(a_1 b_1\), \(a_0 b_1\), \(a_1 b_0\) y \(a_0 b_0\). El genio de Karatsuba consiste en reestructurar el término medio \((a_0 b_1 + a_1 b_0)\) para calcular el producto completo utilizando únicamente 3 multiplicaciones, reduciendo la complejidad global de \(O(n^2)\) a \(O(n^{\log_2 3}) \approx O(n^{1.585})\).

El principio clave radica en sustituir una de las cuatro multiplicaciones requeridas en la forma tradicional por operaciones aditivas y desplazamientos de bits (shifts), los cuales son significativamente más económicos para el procesador. Al aplicar este principio recursivamente a factores cuyas longitudes son potencias de dos (\(n = 2^k\)), la complejidad asintótica se reduce de \(O(n^2)\) a \(O(n^{\log_2 3}) \approx O(n^{1.585})\).

No obstante, el texto enfatiza una consideración práctica crítica para la implementación en C: la recursión introduce una sobrecarga (overhead) debido a la apilamiento de marcos de función (stack frames) y al movimiento de registros. Por esta razón, la implementación real emplea un enfoque híbrido; se establece un umbral (threshold) mediante una macro, de modo que el algoritmo recursivo solo se dispara para números suficientemente grandes, delegando los valores pequeños a la multiplicación o elevación al cuadrado tradicional.

"c₀ := a₀ b₀, c₁ := a₁ b₁, c₂ := (a₀ + a₁)(b₀ + b₁) - c₀ - c₁, then we have ab = B^k (B^k c₁ + c₂) + c₀.

For squaring, this process can be simplified somewhat: With c₀ := a₀², c₁ := a₁², c₂ := (a₀ + a₁)² - c₀ - c₁, we have a² = B^k (B^k c₁ + c₂) + c₀."

En la multiplicación general, el término medio \((a_0 b_1 + a_1 b_0)\) requiere dos multiplicaciones independientes. Karatsuba calcula \((a_0 + a_1)(b_0 + b_1)\) y le resta \(c_0\) y \(c_1\). Como \(c_0\) y \(c_1\) deben calcularse de todos modos para los extremos, el término medio se obtiene mediante sumas y restas, reduciendo las multiplicaciones de \(4\) a \(3\).

Para \(a^2\), los dos factores coinciden (\(a=b\)). Los términos \(c_0 = a_0^2\) y \(c_1 = a_1^2\) son cuadrados puros. El término mixto \(c_2 = (a_0 + a_1)^2 - c_0 - c_1\) se resuelve evaluando una tercera elevación al cuadrado, preservando la simetría y permitiendo reutilizar las rutinas optimizadas de elevación al cuadrado.

"For calculating ab it now appears that only three more multiplications by numbers to base B^k, or 3k² multiplications to base B, are necessary… this yields a total of \(3^{\log_2 n} = n^{\log_2 3} \approx n^{1.585}\) elementary multiplications, as opposed to \(n^2\) in the classical procedure…"

La relación de recurrencia que describe el algoritmo es \(T(n) = 3T(n/2) + O(n)\). Resolviendo mediante el Teorema Maestro, la solución está dominada por el término \(n^{\log_2 3} \approx n^{1.585}\).

A medida que el número de dígitos \(n\) crece (por ejemplo, en claves RSA de 2048 o 4096 bits), la brecha entre \(n^2\) y \(n^{1.585}\) se expande dramáticamente, traduciéndose en reducciones masivas de tiempo de CPU.

"…recursion within a program function always costs something, so that we may hope to experience a savings in time over the classical method… only when the numbers get large. The functions presented below… use the recursive procedure for factors having more than a certain number of digits determined by a macro, while for smaller factors we turn to conventional multiplication…"

Cada llamada recursiva requiere guardar variables en la pila (stack), ajustar punteros y manejar saltos en el flujo de control. Para operandos pequeños (por ejemplo, números de 2 a 8 dígitos base), las operaciones aritméticas de la reestructuración aditiva superan el tiempo que tomaría realizar las \(n^2\) multiplicaciones directas.

Las funciones `kmul()` y `ksqr()` dividen las palabras directamente en memoria (in situ) mediante punteros al dígito menos significativo, evitando copias de buffers. Además, implementan un umbral basado en macros (generalmente llamado `KARATSUBA<sub>CUTOFF</sub>`), debajo del cual el algoritmo conmuta automáticamente a la multiplicación escolar tradicional \(O(n^2)\).

La arquitectura del algoritmo recurre a funciones auxiliares de bajo nivel (mult() y sqr()) denominadas kernel functions cuando no se aplica la recursión. Estas funciones básicas omiten la gestión de direcciones de argumentos idénticos (accumulator mode) o reducciones por desbordamiento (overflow), con el objetivo de maximizar la velocidad de ejecución.

En kmul(), la conmutación hacia el procedimiento recursivo de Karatsuba depende de tres condiciones estrictas:

1. Ambos factores deben poseer exactamente la misma cantidad de dígitos (`len<sub>a</sub> == len<sub>b</sub>`).
2. La cantidad de dígitos debe superar el umbral de eficiencia mínima determinado por la constante `MUL<sub>THRESHOLD</sub>`.
3. El número de dígitos debe ser par (`(0 == (len<sub>a</sub> & 1))`), permitiendo dividir exactamente los operandos en dos mitades de tamaño \(k = n/2\).

Si estas condiciones se cumplen, los operandos se dividen in situ manipulando los punteros `aptr<sub>l</sub>`, `a1ptr<sub>l</sub>`, `bptr<sub>l</sub>` y `b1ptr<sub>l</sub>`, evitando duplicar bloques de memoria y calculando de forma recursiva las componentes \(c_0\) y \(c_1\).

"For the case of nonrecursive multiplication the functions kmul() and ksqr() use the auxiliary functions mult() and sqr(), in which multiplication and squaring are implemented as kernel functions without the support of identical argument addresses (accumulator mode) or reduction in the case of overflow."

Para la base de la recursión (cuando la longitud de los factores cae por debajo de `MUL<sub>THRESHOLD</sub>`), Karatsuba invoca a mult() y sqr().

Estas rutinas internas prescinden de verificaciones adicionales, como comparar si los punteros de entrada y salida apuntan al mismo espacio de memoria (accumulator mode) o aplicar reducciones modulares en caso de overflow. Esta simplificación deliberada permite que el nivel base de la pila de llamadas ejecute las multiplicaciones escolares \(O(n^2)\) a la máxima velocidad posible de la ALU.

"Function: Karatsuba multiplication of two numbers a_l and b_l with 2k digits each to base B Syntax: void kmul (clint *aptr_l, clint *bptr_l, int len_a, int len_b, CLINT p_l); … CLINT c0_l, c1_l; clint c0_l[CLINTMAXSHORT + 2]; clint c1_l[CLINTMAXSHORT + 2]; clint c2_l[CLINTMAXSHORT + 2];"

A diferencia de la función estándar mult_l() (que lee la longitud directamente desde el encabezado CLINT), kmul() recibe punteros directos al dígito menos significativo (`aptr<sub>l</sub>`, `bptr<sub>l</sub>`) junto con sus longitudes explícitas (`len<sub>a</sub>`, `len<sub>b</sub>`). Esto habilita la segmentación de un número en sub-arreglos virtuales sin necesidad de reasignar estructuras dinámicas.

Se reservan arreglos temporales en la pila (c0_l, c1_l, c2_l) dimensionados según la mitad de la capacidad máxima (CLINTMAXSHORT + 2) para alojar los resultados intermedios de los productos de las mitades.

"if ((len_a = len_b) && (len_a > MUL_THRESHOLD) && (0 == (len_a & 1))) { If both factors possess the same even number of digits above the value MUL_THRESHOLD, then recursion is entered with the splitting of the factors into two halves. The pointers aptr_l, a1ptr_l, bptr_l, b1ptr_l are passed to the corresponding least-significant digits of one of the halves."

La expresión `(0 == (len<sub>a</sub> & 1))` verifica si el bit menos significativo de `len<sub>a</sub>` es \(0\), confirmando en un solo ciclo de CPU que la longitud del operando es un entero par.

Para un número de \(2k\) dígitos almacenado consecutivamente en memoria, la mitad de menor peso se ubica en la dirección `aptr<sub>l</sub>`, mientras que la mitad de mayor peso inicia exactamente en `a1ptr<sub>l</sub> = aptr<sub>l</sub> + k`. Al pasar únicamente la nueva dirección base y la longitud \(k\) a las llamadas recursivas de kmul(), el algoritmo divide los factores sin incurrir en copia de datos (zero-copy partitioning).

Para evaluar \(c_2 = (a_0 + a_1)(b_0 + b_1) - c_0 - c_1\), el algoritmo utiliza la función auxiliar addkar() para sumar las mitades de cada factor y luego realiza una llamada recursiva a kmul() sobre estas sumas. Posteriormente, mediante dos restas consecutivas (sub()), aísla el valor definitivo de \(c_2\).

El ensamblaje final del producto \(ab = B^k (B^k c_1 + c_2) + c_0\) se delega a la función auxiliar shiftadd(), la cual realiza la adición aplicando un desplazamiento implícito de \(k\) posiciones en base \(B\).

En caso de que no se cumplan los requisitos iniciales (factores con diferente número de dígitos, longitud impar o tamaño por debajo del umbral), la ejecución pasa al bloque else. Aquí, las secciones de memoria leídas mediante punteros simples se empaquetan en la estructura estándar CLINT asignando la cantidad de dígitos mediante SETDIGITS_L y copiando los bytes con memcpy, para luego ejecutar la multiplicación escolar mult() de nivel kernel.

"The value \(c_2 := (a_0 + a_1)(b_0 + b_1) - c_0 - c_1\) is computed with two additions, a call to kmul(), and two subtractions. The auxiliary function addkar() takes pointers to the least-significant digits of two equally long summands together with their number of digits, and outputs the sum of the two as a CLINT value.

addkar (a1ptr_l, aptr_l, l2, c01_l); addkar (b1ptr_l, bptr_l, l2, c10_l); kmul (LSDPTR_L (c01_l), LSDPTR_L (c10_l), DIGITS_L (c01_l), DIGITS_L (c10_l), c2_l); sub (c2_l, c1_l, tmp_l); sub (tmp_l, c0_l, c2_l);"

Suma las partes alta y baja de cada número (\(a_1 + a_0\) y \(b_1 + b_0\)). Como esta suma puede producir un dígito extra de acarreo, el resultado se almacena formalmente en tipos CLINT (c01_l y c1_l) para gestionar una posible longitud de \(l2 + 1\).

Se invoca kmul() pasando los punteros al inicio de c01_l y c1_l.

Con dos operaciones de sustracción (sub), se descuentan \(c_1\) y \(c_0\) del producto acumulado, obteniendo \((a_0 + a_1)(b_0 + b_1) - c_1 - c_0 = a_0 b_1 + a_1 b_0\).

"The function branch ends with the calculation of \(B^k (B^k c_1 + c_2) + c_0\), which used the auxiliary function shiftadd(), which during the addition left shifts the first of the two CLINT summands by a given number of places to base B.

shiftadd (c1_l, c2_l, l2, tmp_l); shiftadd (tmp_l, c0_l, l2, p_l); }"

Evaluar \(B^k X + Y\) requiere multiplicar \(X\) por \(B^k\) (desplazar \(k\) dígitos a la izquierda) y sumar \(Y\).

La función shiftadd(X, Y, k, R) realiza ambas tareas en una sola pasada de memoria: escribe los primeros \(k\) dígitos de \(Y\) directamente en el resultado y luego acumula \(X + Y_{\text{restante}}\) a partir de la posición \(k\), evitando copias intermedias en búferes temporales.

"If one of the input conditions is not fulfilled, the recursion is interrupted and the nonrecursive multiplication mult() is called. As a requirement for calling mult() the two factor halves in aptr_l and bptr_l are brought into CLINT format.

else { memcpy (LSDPTR_L (c1_l), aptr_l, len_a * sizeof (clint)); memcpy (LSDPTR_L (c2_l), bptr_l, len_b * sizeof (clint)); SETDIGITS_L (c1_l, len_a); SETDIGITS_L (c2_l, len_b); mult (c1_l, c2_l, p_l); RMLDZRS_L (p_l); }"

Dado que los parámetros aptr_l y bptr_l eran punteros simples a arreglos en memoria (sin el encabezado de longitud que exige la estructura CLINT), el caso else debe copiar los bloques de memoria crudos a variables temporales c1_l y c2_l.

`SETDIGITS<sub>L</sub>` asigna manualmente `len<sub>a</sub>` y `len<sub>b</sub>` en el primer elemento de la estructura CLINT para reconstruir un número válido.

Con las estructuras normalizadas, se invoca a mult() para ejecutar la multiplicación escolar tradicional \(O(n^2)\) y se eliminan los ceros a la izquierda residuales con RMLDZRS_L.

Para evaluar \(c_2 = (a_0 + a_1)(b_0 + b_1) - c_0 - c_1\), el algoritmo utiliza la función auxiliar addkar() para sumar las mitades de cada factor y luego realiza una llamada recursiva a kmul() sobre estas sumas. Posteriormente, mediante dos restas consecutivas (sub()), aísla el valor definitivo de \(c_2\).

El ensamblaje final del producto \(ab = B^k (B^k c_1 + c_2) + c_0\) se delega a la función auxiliar shiftadd(), la cual realiza la adición aplicando un desplazamiento implícito de \(k\) posiciones en base \(B\).

En caso de que no se cumplan los requisitos iniciales (factores con diferente número de dígitos, longitud impar o tamaño por debajo del umbral), la ejecución pasa al bloque else. Aquí, las secciones de memoria leídas mediante punteros simples se empaquetan en la estructura estándar CLINT asignando la cantidad de dígitos mediante SETDIGITS_L y copiando los bytes con memcpy, para luego ejecutar la multiplicación escolar mult() de nivel kernel.

"The value \(c_2 := (a_0 + a_1)(b_0 + b_1) - c_0 - c_1\) is computed with two additions, a call to kmul(), and two subtractions. The auxiliary function addkar() takes pointers to the least-significant digits of two equally long summands together with their number of digits, and outputs the sum of the two as a CLINT value.

addkar (a1ptr_l, aptr_l, l2, c01_l); addkar (b1ptr_l, bptr_l, l2, c10_l); kmul (LSDPTR_L (c01_l), LSDPTR_L (c10_l), DIGITS_L (c01_l), DIGITS_L (c10_l), c2_l); sub (c2_l, c1_l, tmp_l); sub (tmp_l, c0_l, c2_l);"

Operación con `addkar()`: Suma las partes alta y baja de cada número (\(a_1 + a_0\) y \(b_1 + b_0\)). Como esta suma puede producir un dígito extra de acarreo, el resultado se almacena formalmente en tipos CLINT (c01_l y c1_l) para gestionar una posible longitud de \(l2 + 1\).

Multiplicación Intermedia: Se invoca kmul() pasando los punteros al inicio de c01_l y c1_l.

Aislamiento por Resta: Con dos operaciones de sustracción (sub), se descuentan \(c_1\) y \(c_0\) del producto acumulado, obteniendo \((a_0 + a_1)(b_0 + b_1) - c_1 - c_0 = a_0 b_1 + a_1 b_0\).

"The function branch ends with the calculation of \(B^k (B^k c_1 + c_2) + c_0\), which used the auxiliary function shiftadd(), which during the addition left shifts the first of the two CLINT summands by a given number of places to base B.

shiftadd (c1_l, c2_l, l2, tmp_l); shiftadd (tmp_l, c0_l, l2, p_l); }"

Evaluar \(B^k X + Y\) requiere multiplicar \(X\) por \(B^k\) (desplazar \(k\) dígitos a la izquierda) y sumar \(Y\).

La función shiftadd(X, Y, k, R) realiza ambas tareas en una sola pasada de memoria: escribe los primeros \(k\) dígitos de \(Y\) directamente en el resultado y luego acumula \(X + Y_{\text{restante}}\) a partir de la posición \(k\), evitando copias intermedias en búferes temporales.

"If one of the input conditions is not fulfilled, the recursion is interrupted and the nonrecursive multiplication mult() is called. As a requirement for calling mult() the two factor halves in aptr_l and bptr_l are brought into CLINT format.

else { memcpy (LSDPTR_L (c1_l), aptr_l, len_a * sizeof (clint)); memcpy (LSDPTR_L (c2_l), bptr_l, len_b * sizeof (clint)); SETDIGITS_L (c1_l, len_a); SETDIGITS_L (c2_l, len_b); mult (c1_l, c2_l, p_l); RMLDZRS_L (p_l); }"

Empaquetado explícito con `memcpy`: Dado que los parámetros aptr_l y bptr_l eran punteros simples a arreglos en memoria (sin el encabezado de longitud que exige la estructura CLINT), el caso else debe copiar los bloques de memoria crudos a variables temporales c1_l y c2_l.

Inicialización de Encabezados: `SETDIGITS<sub>L</sub>` asigna manualmente `len<sub>a</sub>` y `len<sub>b</sub>` en el primer elemento de la estructura CLINT para reconstruir un número válido.

Con las estructuras normalizadas, se invoca a mult() para ejecutar la multiplicación escolar tradicional \(O(n^2)\) y se eliminan los ceros a la izquierda residuales con RMLDZRS_L.